Delete Columns to Make Sorted II

Delete Columns to Make Sorted II

What is this problem about?

The Delete Columns to Make Sorted II interview question is a greedy string optimization problem. You are given a grid of equal-length strings. You need to delete the minimum number of columns such that the remaining characters in each row, when read as a full word, form a list that is lexicographically sorted. Unlike the first version, a column only needs to be "sorted" if the rows aren't already distinguished by a previous column. This Delete Columns to Make Sorted II coding problem is a test of row-dependency logic.

Why is this asked in interviews?

Google uses this to test a candidate's ability to maintain state across column traversals. It evaluates if you can distinguish between "columns that must be sorted" and "columns where row order is already finalized." It’s a higher-level grid problem that requires careful boolean tracking.

Algorithmic pattern used

This utilizes the Array, String, Greedy interview pattern.

1. State Tracking: Maintain a boolean array isSorted[i] which is true if the i-th row is already lexicographically smaller than the (i+1)-th row.
2. Greedy Check: Iterate through columns one by one.
3. Validation: For the current column, check every adjacent row pair (i, i+1).
   • If isSorted[i] is true, we don't care about the current column for this pair.
   • If grid[i][j] > grid[i+1][j], this column is "bad." Delete it and move to the next column.
4. Finalization: If the column is "good," update isSorted for all pairs where grid[i][j] < grid[i+1][j].

Example explanation

Grid: ["ca", "bb", "ac"]

1. Col 0: 'c', 'b', 'a'. Since 'c' > 'b' and 'b' > 'a', this column is bad. Delete it.
2. Col 1: 'a', 'b', 'c'. This is sorted. Keep it. Answer: 1. If the grid was ["aa", "ab", "ba"]:
3. Col 0: 'a', 'a', 'b'. 'a' <= 'a' and 'a' < 'b'. Good. isSorted[1] becomes true.
4. Col 1: 'a', 'b', 'a'. Pair 0 ('a', 'b') is fine. Pair 1 is already isSorted. Good. Answer: 0.

Common mistakes candidates make

• Ignoring Dependency: Thinking every column must be individually sorted.
• Incorrect Update: Updating the isSorted array while checking the column, instead of after the entire column is validated.
• Complexity: Trying to use recursion when a single pass through the columns is O(Cols * Rows).

Interview preparation tip

Whenever row order depends on multiple columns, use a "finalized" or "sorted" flag for each row pair. Once a pair is strictly ordered (e.g., 'a' < 'b'), the values in subsequent columns for that pair no longer matter.