Delete Columns to Make Sorted - Solution & Explanation
Problem Statement
You are given an array of n strings strs, all of the same length.
The strings can be arranged such that there is one on each line, making a grid.
- For example,
strs = ["abc", "bce", "cae"]can be arranged as follows:
abc bce cae
You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e') are sorted, while column 1 ('b', 'c', 'a') is not, so you would delete column 1.
Return the number of columns that you will delete.
Example 1:
Input: strs = ["cba","daf","ghi"] Output: 1 Explanation: The grid looks as follows: cba daf ghi Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.
Example 2:
Input: strs = ["a","b"] Output: 0 Explanation: The grid looks as follows: a b Column 0 is the only column and is sorted, so you will not delete any columns.
Example 3:
Input: strs = ["zyx","wvu","tsr"] Output: 3 Explanation: The grid looks as follows: zyx wvu tsr All 3 columns are not sorted, so you will delete all 3.
Constraints:
n == strs.length1 <= n <= 1001 <= strs[i].length <= 1000strs[i]consists of lowercase English letters.
Approach Overview
Problem Overview: You get an array of equal-length strings. Each column is formed by taking characters at the same index from every string. The task is to count how many columns must be deleted so that every remaining column is lexicographically sorted from top to bottom.
Approach 1: Brute Force, Column-wise Check (Time: O(n * m), Space: O(1))
Iterate column by column and verify whether the characters in that column are sorted across all rows. For column j, compare adjacent rows strs[i][j] and strs[i+1][j]. If any pair violates lexicographic order (i.e., strs[i][j] > strs[i+1][j]), the column must be deleted. Continue this check for every column and count the violations.
This approach treats each column independently and performs a full scan across rows every time. No extra data structures are required since comparisons happen directly on characters inside the strings. The algorithm relies on simple iteration over a 2D grid of characters, making it easy to implement using basic array traversal and string indexing.
Approach 2: Optimized Single Pass Check (Time: O(n * m), Space: O(1))
The optimized version follows the same column-wise traversal but exits early as soon as a violation is detected. While scanning column j, the moment strs[i][j] > strs[i+1][j] appears, the column is marked for deletion and the loop breaks immediately. This avoids unnecessary comparisons for the rest of that column.
The key idea is recognizing that one violation is enough to invalidate the column. Early termination reduces the constant factor in practice, especially when unsorted columns appear frequently. You still iterate across all columns, but many columns stop scanning after only a few comparisons.
This approach still uses simple character comparisons and sequential traversal, which keeps memory usage constant. It works well for typical interview constraints where the number of rows and columns can both be moderately large.
Recommended for interviews: The optimized single-pass check is what interviewers expect. It shows that you recognize the independence of each column and apply an early break when a violation appears. Starting with the brute-force explanation demonstrates clear reasoning, while the optimized version shows attention to efficiency and clean iteration over arrays of strings.
Approach 1: Approach 1: Brute Force, Column-wise Check
This approach involves iterating over each column in the grid formed by the strings. For each column, we compare the characters from top to bottom to ensure that they are in non-decreasing order. If a column is found to be unsorted, it needs to be deleted. We maintain a count of such unsorted columns and return this count at the end.
We start by computing the number of columns using the length of the first string. Then, we iterate over each column, and for each column, we check if it is sorted by comparing each element with its predecessor. If a descending pair is found, we increment the deletion count and break out of the loop for that column since it's unsorted.
Complexity
Time Complexity: O(m * n), where m is the number of strings and n is the length of each string. We iterate over each column and each row within the column.
Space Complexity: O(1), no additional space is used except for a few variables.
Approach 2: Approach 2: Optimized Single Pass Check
In this approach, instead of checking each column individually with a nested loop, we try to reduce the checks by using internal helper functions or flags. This might reduce the overhead for checking conditions multiple times, though generally both approaches might occupy similar time complexity due to the input constraints.
This C implementation checks each column with the help of a boolean flag to optimize the escape from the nested loop once an unsorted column is detected, reducing unnecessary further checks for that column.
Complexity
Time Complexity: O(m * n)
Space Complexity: O(1)
Approach 3: Compare Column by Column
We denote the number of rows in the string array strs as n, and the number of columns as m.
We traverse each column, starting from the second row, and compare the character of the current row with that of the previous row column by column. If the character of the current row is less than that of the previous row, it indicates that the current column is not arranged in non-strictly increasing lexicographical order, and we need to delete it, incrementing the result by one, then break out of the inner loop.
Finally, we return the result.
The time complexity is O(L), where L is the total length of the strings in the array strs. The space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force, Column-wise Check | Time Complexity: O(m * n), where m is the number of strings and n is the length of each string. We iterate over each column and each row within the column. Space Complexity: O(1), no additional space is used except for a few variables. |
| Approach 2: Optimized Single Pass Check | Time Complexity: O(m * n) Space Complexity: O(1) |
| Compare Column by Column | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force, Column-wise Check | O(n * m) | O(1) | Good for understanding the problem. Simple full scan of each column. |
| Optimized Single Pass Check | O(n * m) | O(1) | Preferred in interviews. Stops scanning a column immediately after detecting an order violation. |
Video Solution
Delete Columns to Make Sorted | MICROSOFT | Leetcode 944 | codestorywithMIK • codestorywithMIK • 12,422 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Delete Columns to Make Sorted easy or hard?
Delete Columns to Make Sorted Python/Java solution
How to solve Delete Columns to Make Sorted in O(n)?
What is the best approach for Delete Columns to Make Sorted?
Is Delete Columns to Make Sorted asked at Google/Amazon/Meta?
What data structure is used in Delete Columns to Make Sorted?
What is the time complexity of Delete Columns to Make Sorted?
Ready to solve this problem?
Practice Delete Columns to Make Sorted with our built-in code editor and test cases.
Practice on FleetCode