Watch 10 video solutions for Delete Columns to Make Sorted, a easy level problem involving Array, String. This walkthrough by codestorywithMIK has 11,516 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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.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 | 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. |