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.length1 <= n <= 1001 <= strs[i].length <= 100strs[i] consists of lowercase English letters.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.
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.
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.
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.
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.
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]):
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;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.
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n*m), where n is the number of strings and m is the length of each string. |
| Dynamic Programming Approach | Time Complexity: O(m*n^2), where m is the number of strings and n is the length of each string. |
| Greedy | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Column Validation | O(m * n) | O(m) | Best general solution; efficient for large column counts |
| Dynamic Programming on Columns | O(n^2 * m) | O(n) | Useful for understanding column subsequence formulation |
Delete Columns to Make Sorted II | Minute Details Covered | Dry Run | Leetcode 955 | MIK • codestorywithMIK • 8,258 views views
Watch 9 more video solutions →Practice Delete Columns to Make Sorted II with our built-in code editor and test cases.
Practice on FleetCode