Skip to main content
Talentd

Delete Columns to Make Sorted II - Solution & Explanation

MediumArrayStringGreedy24 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

You are given an array of n strings strs, all of the same length.

We may choose any deletion indices, and we delete all the characters in those indices for each string.

For example, if we have strs = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef", "vyz"].

Suppose we chose a set of deletion indices answer such that after deletions, the final array has its elements in lexicographic order (i.e., strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Return the minimum possible value of answer.length.

 

Example 1:

Input: strs = ["ca","bb","ac"]
Output: 1
Explanation: 
After deleting the first column, strs = ["a", "b", "c"].
Now strs is in lexicographic order (ie. strs[0] <= strs[1] <= strs[2]).
We require at least 1 deletion since initially strs was not in lexicographic order, so the answer is 1.

Example 2:

Input: strs = ["xc","yb","za"]
Output: 0
Explanation: 
strs is already in lexicographic order, so we do not need to delete anything.
Note that the rows of strs are not necessarily in lexicographic order:
i.e., it is NOT necessarily true that (strs[0][0] <= strs[0][1] <= ...)

Example 3:

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: We have to delete every column.

 

Constraints:

  • n == strs.length
  • 1 <= n <= 100
  • 1 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

Approach Overview

Problem Overview: You are given an array of equal-length strings. You may delete any column. The goal is to remove the minimum number of columns so the rows remain lexicographically sorted from top to bottom.

Approach 1: Greedy Column Validation (O(m*n) time, O(m) space)

This approach scans columns from left to right and greedily decides whether a column must be deleted. Maintain an array sorted where sorted[i] indicates whether row i is already confirmed to be lexicographically smaller than row i+1. For each column, check every unresolved adjacent pair. If a column causes strs[i][col] > strs[i+1][col], the column must be deleted. Otherwise, update pairs that become strictly ordered. The key insight: once a pair is confirmed sorted, future columns cannot invalidate it. This prevents unnecessary comparisons and ensures each column is processed once.

The greedy rule works because lexicographic order is determined by the first differing character. If a column breaks order for an unresolved pair, keeping it would permanently violate sorting. This makes deletion the only safe choice. The algorithm iterates through array columns and performs character comparisons across rows, making it efficient even when string length grows.

Approach 2: Dynamic Programming on Columns (O(n^2 * m) time, O(n) space)

The dynamic programming view treats each column as a potential element in a valid subsequence of columns that preserves lexicographic order. Define dp[c] as the maximum number of columns that can end with column c. For every earlier column p, check whether keeping both columns maintains non-decreasing characters for every row: strs[r][p] <= strs[r][c]. If valid, update dp[c] = max(dp[c], dp[p] + 1). The longest valid column subsequence determines how many columns you can keep, and the rest must be deleted.

This approach resembles a longest increasing subsequence over columns but validated across all rows simultaneously. It relies heavily on repeated comparisons across rows of the string matrix. While conceptually clean, the quadratic column comparisons make it slower than the greedy strategy for large inputs.

Recommended for interviews: The greedy approach is the expected solution. It uses a simple observation about lexicographic ordering and avoids unnecessary checks once row pairs become fixed. The DP approach demonstrates deeper reasoning about column subsequences, but its O(n^2 * m) complexity is rarely preferred when the greedy greedy solution achieves optimal performance.

Approach 1: Greedy Approach

In this approach, we iterate through each column and check if any column violates the lexicographic order of rows. If we find such a column, we mark it for deletion. We need to ensure that any deletion does not affect previously sorted columns.

The C solution utilizes a greedy approach where we iteratively check columns for validity. The `isSorted` array keeps track of which rows are already sorted by examining previously considered columns. If any row pair in a column is out of order and previously non-determined, the column is marked for deletion.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n*m), where n is the number of strings and m is the length of each string.
Space Complexity: O(n), for storing sorting status of the rows.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

This approach involves creating a dynamic programming table to maintain possible sequences that keep the strings sorted. We try to find and maintain the minimum deletions required while ensuring each column is evaluated with consideration to previously processed columns.

The C solution uses dynamic programming, where `dp[j]` holds the minimum deletions needed for making columns up to `j` sorted. The solution compares each column with possible previous columns that could lead to a sorting result with minimal deletions and builds upon that result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m*n^2), where m is the number of strings and n is the length of each string.
Space Complexity: O(n), accounting for the dynamic programming array to store intermediate results.

Try this approach in the editor →

Approach 3: Greedy

When comparing strings in lexicographical order, we compare from left to right, and the first unequal character determines the ordering relationship between two strings. Therefore, we can traverse each column from left to right and determine whether the current column needs to be deleted.

We maintain a boolean array st of length n - 1, indicating whether the ordering relationship between adjacent string pairs has been determined. If the ordering relationship has been determined, then any subsequent character comparison between these two strings will not change their ordering relationship.

For each column j, we traverse all adjacent string pairs (strs[i], strs[i + 1]):

  • If st[i] is false and strs[i][j] > strs[i + 1][j], it means the current column must be deleted. We increment the answer by one and skip processing this column;
  • Otherwise, if st[i] is false and strs[i][j] < strs[i + 1][j], it means the current column determines the ordering relationship between these two strings. We set st[i] to true.

After traversing all columns, the answer is the number of columns that need to be deleted.

This greedy strategy is optimal because lexicographical order is determined by the first different column from left to right. If the current column is not deleted and causes incorrect ordering for some string pair, then regardless of subsequent columns, this error cannot be corrected, so the current column must be deleted. If the current column is not deleted and does not cause incorrect ordering for any string pair, then keeping the current column will not affect the final lexicographical ordering relationship.

The time complexity is O(n times m) and the space complexity is O(n), where n and m are the length of the string array and the length of each string, respectively.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach

Time Complexity: O(n*m), where n is the number of strings and m is the length of each string.
Space Complexity: O(n), for storing sorting status of the rows.

Dynamic Programming Approach

Time Complexity: O(m*n^2), where m is the number of strings and n is the length of each string.
Space Complexity: O(n), accounting for the dynamic programming array to store intermediate results.

Greedy—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Column ValidationO(m * n)O(m)Best general solution; efficient for large column counts
Dynamic Programming on ColumnsO(n^2 * m)O(n)Useful for understanding column subsequence formulation

Video Solution

Delete Columns to Make Sorted II | Minute Details Covered | Dry Run | Leetcode 955 | MIK • codestorywithMIK • 8,543 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Delete Columns to Make Sorted II easy or hard?
Delete Columns to Make Sorted II is rated Medium difficulty. The challenge is recognizing that lexicographic order depends only on the first differing column and that resolved row pairs never need to be checked again. Once this observation is made, the greedy O(m*n) solution becomes straightforward.
How to solve Delete Columns to Make Sorted II in O(n)?
The problem can be solved in O(m*n) time using a greedy column scan. Maintain a boolean array tracking row pairs already sorted. For each column, check unresolved pairs; if any pair violates lexicographic order, delete the column. Otherwise update the pairs that become strictly ordered after this column.
Delete Columns to Make Sorted II Python or Java solution?
Both Python and Java implementations follow the same greedy idea: iterate column by column, check violations among unresolved row pairs, and update a boolean array when pairs become sorted. The algorithm structure remains identical across Python, Java, C++, C#, and JavaScript.
What is the best approach for Delete Columns to Make Sorted II?
The greedy column validation approach is the most efficient solution. Scan columns from left to right and track which adjacent rows are already lexicographically ordered. If a column violates ordering for any unresolved pair, delete it; otherwise mark pairs that become sorted. This runs in O(m*n) time and O(m) space, where m is the number of rows and n is the number of columns.
Is Delete Columns to Make Sorted II asked at Google/Amazon/Meta?
String ordering and greedy validation problems like this appear in interviews at companies such as Google, Amazon, and Meta. Variants that involve lexicographic constraints, column deletions, or maintaining sorted order are common in mid-level algorithm interviews.
What data structure is used in Delete Columns to Make Sorted II?
The solution mainly uses arrays and strings. A boolean array tracks which adjacent row pairs are already confirmed sorted, and character comparisons are performed directly on the string matrix. No complex data structures are required.
What is the time complexity of Delete Columns to Make Sorted II?
The optimal greedy solution runs in O(m * n) time because each column is scanned once and compared across adjacent rows. Space complexity is O(m) for tracking which row pairs are already confirmed sorted. A dynamic programming alternative takes O(n^2 * m) time due to pairwise column checks.

Ready to solve this problem?

Practice Delete Columns to Make Sorted II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays