Delete Columns to Make Sorted II

main.md

Question

Approach

I process the strings column by column from left to right. I keep track of which adjacent string pairs are already confirmed to be in correct lexicographic order.

For each column:

• I check all unconfirmed adjacent pairs.
• If any pair violates lexicographic order (strs[i][c] > strs[i+1][c]), I must delete this column.
• If the column is safe, I mark pairs where strs[i][c] < strs[i+1][c] as confirmed.

Implementation

Complexities

• Time: O(n x m)
• Space: O(n)