Delete Columns to Make Sorted III - Solution & Explanation
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 every string (row) in lexicographic order. (i.e., (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]), and (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]), and so on). Return the minimum possible value of answer.length.
Example 1:
Input: strs = ["babca","bbazb"] Output: 3 Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"]. Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]). Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.
Example 2:
Input: strs = ["edcba"] Output: 4 Explanation: If we delete less than 4 columns, the only row will not be lexicographically sorted.
Example 3:
Input: strs = ["ghi","def","abc"] Output: 0 Explanation: All rows are already lexicographically sorted.
Constraints:
n == strs.length1 <= n <= 1001 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
Approach Overview
Problem Overview: You are given an array of equal-length strings. Each column represents characters from all rows at the same index. The goal is to delete the minimum number of columns so that every row becomes lexicographically non‑decreasing from left to right.
The key observation: after deletions, the remaining columns must form a sequence where every row stays sorted. Instead of directly deciding which columns to remove, treat it as finding the longest valid sequence of columns that keeps all rows sorted. The answer is total columns minus that sequence length.
Approach 1: Dynamic Programming (Column LIS) (Time: O(m² * n), Space: O(m))
This is the standard optimal approach. Treat each column like an element in a Longest Increasing Subsequence problem. Let dp[j] represent the maximum number of valid columns ending at column j. For every pair of columns i < j, check whether column i can appear before column j. This requires verifying that for every row r, strs[r][i] <= strs[r][j]. If the condition holds for all rows, update dp[j] = max(dp[j], dp[i] + 1). The longest valid subsequence across columns gives the maximum columns we can keep. The minimum deletions become m - max(dp). This method leverages Dynamic Programming and works well because column count is usually small enough for the quadratic comparison.
Approach 2: Greedy with Column Comparison (Time: O(m² * n), Space: O(1))
This strategy incrementally builds a set of kept columns. For each new column, compare it with previously kept columns to verify whether adding it preserves lexicographic order across every row. The algorithm iterates through rows and checks character ordering for each candidate pair of columns. If any row violates the order, that column must be skipped (effectively deleted). While conceptually simple, repeated column comparisons can still lead to quadratic checks over columns. It relies heavily on character comparisons within the String structure and column traversal through the Array of strings.
Recommended for interviews: The dynamic programming formulation is what most interviewers expect. Recognizing that the problem reduces to a longest increasing subsequence across columns demonstrates strong problem decomposition. The greedy comparison approach helps build intuition but doesn’t clearly express the optimal subsequence structure. Showing both ideas — brute reasoning followed by the DP optimization — signals solid algorithmic thinking.
Approach 1: Dynamic Programming Approach
This approach utilizes dynamic programming to identify the minimum columns to delete to make each row lexicographically sorted. The key idea is to use a dp array where dp[j] represents the length of the longest increasing subsequence of columns ending at index j.
We'll iterate over each column and compare with the previous columns to update the dp array by checking each row for their lexicographic order. We finally return the total number of columns minus the maximum value in the dp array, which gives the least number of deletions needed.
The C code implements a dynamic programming solution. It initializes a dp array to track the longest increasing subsequence of column indices which maintain the row order. For each pair of columns, it checks if swapping the columns maintains the lexicographic order in each row. The solution updates the dp array accordingly and returns the total columns minus the maximum value in this array.
Complexity
Time Complexity: O(n^2 * m), where n is the length of each string and m is the number of strings.
Space Complexity: O(n) for the dp array.
Approach 2: Greedy Approach with Column Comparison
This approach involves a greedy strategy where we incrementally build the sorted subset of columns. By comparing columns, we find those that necessarily break the order when removed and only retain these to maintain row order.
At each step, the algorithm compares characters in successive columns, choosing deletions based on maintaining an overall least sequence of lexicographically ordered characters per row.
In this greedy C solution, we traverse each column, comparing successive characters for lexicographic order. If for any column, the order breaks, the column is marked for deletion, thereby incrementing the answer tally, which is returned as the result.
Complexity
Time Complexity: O(m * n), where m is the number of strings and n is the length of each string.
Space Complexity: O(1), as only constant space is used.
Approach 3: Dynamic Programming
We define f[i] as the length of the longest non-decreasing subsequence ending at column i. Initially, f[i] = 1, and the final answer is n - max(f).
To compute f[i], we iterate over all j < i. If for all strings s, we have s[j] leq s[i], then we update f[i] as follows:
$ f[i] = max(f[i], f[j] + 1)
Finally, we return n - max(f).
The time complexity is O(n^2 times m), and the space complexity is O(n), where n is the length of each string in the array strs, and m$ is the number of strings in the array.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2 * m), where n is the length of each string and m is the number of strings. |
| Greedy Approach with Column Comparison | Time Complexity: O(m * n), where m is the number of strings and n is the length of each string. |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Column LIS) | O(m² * n) | O(m) | General case and interview settings where optimal subsequence detection is required |
| Greedy Column Comparison | O(m² * n) | O(1) | Conceptual approach for understanding column ordering without maintaining DP state |
Video Solution
Delete Columns to Make Sorted III | Hard Made Easy | Dry Run | Leetcode 960 | codestorywithMIK • codestorywithMIK • 6,301 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Delete Columns to Make Sorted III easy or hard?
Delete Columns to Make Sorted III Python/Java solution
How to solve Delete Columns to Make Sorted III in O(n)?
What is the best approach for Delete Columns to Make Sorted III?
Is Delete Columns to Make Sorted III asked at Google/Amazon/Meta?
What data structure is used in Delete Columns to Make Sorted III?
What is the time complexity of Delete Columns to Make Sorted III?
Ready to solve this problem?
Practice Delete Columns to Make Sorted III with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor