Delete Columns to Make Sorted
What is this problem about?
The Delete Columns to Make Sorted interview question gives you a grid of strings (all of the same length). Imagine the strings are stacked on top of each other. You need to find the number of columns that are not sorted lexicographically (from top to bottom). You want to return the count of these "bad" columns. This Delete Columns to Make Sorted coding problem is a basic grid traversal task.
Why is this asked in interviews?
Google and Amazon use this to check for basic 2D array navigation skills. It tests if a candidate can correctly iterate through columns first, then rows (the inverse of standard reading order). It’s a foundational test of nested loop control and comparison logic.
Algorithmic pattern used
This follows the Array, String interview pattern.
- Inverse Traversal: Iterate through the column indices (j = 0 to width-1).
- Column Scan: For each column, iterate through the row indices (i = 1 to height-1).
- Check Order: Compare the character at grid[i][j] with the one at grid[i-1][j].
- Count: If any character is smaller than the one above it, increment the deletion count and move to the next column.
Example explanation
Grid:
"abc"
"bce"
"cae"
- Col 0: 'a', 'b', 'c' (Sorted).
- Col 1: 'b', 'c', 'a' ('a' < 'c', NOT Sorted).
- Col 2: 'c', 'e', 'e' (Sorted).
Answer: 1.
Common mistakes candidates make
- Row-First Traversal: Accidental iteration through rows first, which makes comparing column values much more complex.
- Double Counting: Failing to break the inner loop once a column is determined to be bad, leading to multiple counts for the same column.
- Lexicographical confusion: Forgetting how character comparison works (e.g., 'a' < 'b').
Interview preparation tip
When working with grids of strings, visualize the column as a separate word. If the problem asks for column-wise properties, always put the column loop on the outside.
