Delete Columns to Make Sorted

Reading the grid. strs[r][c] is the letter in row r, column c: first pick the string, then the position inside it. So column c is strs[0][c], strs[1][c], …, strs[n − 1][c], and the number of columns is the length of each string, m = len(strs[0]).

Comparing letters. In code, a letter is stored as a number, its character code, and comparing two letters compares those numbers. The lowercase letters have codes in alphabetical order: 'a' is 97, 'b' is 98, and so on up to 'z' at 122. So for two letters, x > y means exactly "x comes later in the alphabet than y".

Each column is decided on its own. Deleting a column removes only that column's letters; every other column keeps exactly the letters it had. So there is nothing to choose or plan: the answer is simply the number of columns that are not sorted. (There are harder versions of this problem where the rows, read as whole words, must end up in order. There, deletions do affect each other. Here they do not.)

Start from the definition. A column is sorted when every letter is at most every letter below it. So check exactly that: for every pair of rows i < j, compare strs[i][c] with strs[j][c]. As soon as one pair has the upper letter later in the alphabet, the column is not sorted, and its remaining pairs do not need to be looked at.

We trace Example 1, strs = ["ape", "bee", "rye", "gum"]. The two cells being compared light up in blue. Once a column is decided, it turns green if it stays and orange if it is deleted.

Step 1: Write the strings one under another: 4 rows and 3 columns. deleted starts at 0.

Step 2: Column 0, rows 0 and 1: a and b, in order.

Step 3: Column 0, rows 0 and 2: a and r, in order.

Step 4: Column 0, rows 0 and 3: a and g, in order.

Step 5: Column 0, rows 1 and 2: b and r, in order.

Step 6: Column 0, rows 1 and 3: b and g, in order.

Step 7: Column 0, rows 2 and 3: r is above g but comes later, out of order. Column 0 is deleted (deleted = 1).

Step 8: Column 1, rows 0 and 1: p is above e but comes later, out of order. Column 1 is deleted (deleted = 2); its other 5 pairs are skipped.

Step 9: Column 2, rows 0 and 1: e and e, the same letter, allowed.

Step 10: Column 2, rows 0 and 2: e and e, the same letter, allowed.

Step 11: Column 2, rows 0 and 3: e and m, in order.

Step 12: Column 2, rows 1 and 2: e and e, the same letter, allowed.

Step 13: Column 2, rows 1 and 3: e and m, in order.

Step 14: Column 2, rows 2 and 3: e and m, in order. All 6 pairs are in order, so column 2 stays.

Step 15: Columns 0 and 1 are deleted and column 2 stays. Return 2, after 13 comparisons.

1. Set deleted = 0. Let m be the length of each string.
2. For each column c from 0 to m − 1:
   • For every pair of rows i < j: if strs[i][c] > strs[j][c], the column is not sorted. Add 1 to deleted and go straight to the next column.
3. Return deleted.

Let n be the number of strings (the rows) and m their length (the columns).

Time Complexity: O(m · n²). A column has n(n − 1)/2 pairs of rows, 6 for 4 rows and 4,950 for 100 rows, and a sorted column has every one of them checked.

Space Complexity: O(1). Only a counter and loop indexes.

A column is sorted exactly when putting it in order changes nothing. So for each column, copy its letters into a list, sort a second copy, and compare the two lists position by position. If they are the same, the column was already in order and stays. If they differ anywhere, some letter was out of place and the column is deleted.

Equal letters cause no trouble. Sorting keeps equal letters side by side, so a column like e, e, e, m sorts to itself and stays.

In Python, zip(*strs) hands you the columns directly: list(zip("ape", "bee")) is [('a', 'b'), ('p', 'e'), ('e', 'e')]. The code below builds each column by hand so that it reads the same in all three languages.

We trace Example 1 again. The top row is the column as read down the grid; the row under it is its sorted copy. Positions where the two lists agree turn green, and the first position where they differ turns orange. The last frame lists the three columns with their verdicts.

Step 1: Copy column 0: a, b, r, g.

Step 2: Its sorted copy is a, b, g, r. They differ at row 2 (r against g), so column 0 is deleted (deleted = 1).

Step 3: Copy column 1: p, e, y, u.

Step 4: Its sorted copy is e, p, u, y. They differ at row 0 (p against e), so column 1 is deleted (deleted = 2).

Step 5: Copy column 2: e, e, e, m.

Step 6: Its sorted copy is e, e, e, m, identical, so column 2 stays.

Step 7: Two columns changed when sorted. Return 2.

1. Set deleted = 0.
2. For each column c:
   • Build column, the letters strs[0][c], strs[1][c], …, strs[n − 1][c].
   • Build sorted_copy, a sorted copy of column.
   • If column and sorted_copy differ, add 1 to deleted.
3. Return deleted.

Time Complexity: O(m · n log n). Each column is copied in O(n) and sorted in O(n log n). (Python's sort first looks for stretches that are already in order, so on a column that is already sorted it needs only one pass.)

Space Complexity: O(n). The column and its sorted copy, rebuilt for every column.

Keep the early stop of the pair check and the low cost of a single pass, with no copies. Two ideas do it.

Idea 1: checking neighbours is enough. Compare each letter only with the letter directly below it. This decides the column in both directions.

• If every letter is at most the one below it, the column is sorted. The steps chain together. In e, e, e, m, e ≤ e, e ≤ e and e ≤ m, so the top e is at most everything below it, and the same holds for every other letter. The far-apart pairs never need a check of their own.
• If some pair is out of order, some step between them goes backwards. Say row i holds a letter later than row j further down. Reading down from i to j, the letters start later and end earlier, and forward-or-equal steps alone can never reach an earlier letter, so at least one step between them goes backwards. In column 2 of Example 3, p, p, n, the far pair p over n is out of order, and so is the step p → n.

So a column is sorted exactly when none of its n − 1 neighbouring steps goes backwards.

Idea 2: stop at the first backwards step. One backwards step is enough to delete a column, and nothing further down can undo it. So leave the column right there and move to the next one.

Together: at most n − 1 comparisons per column instead of n(n − 1)/2, often just one or two, and no extra memory.

We trace Example 1 one last time. Only a letter and the letter directly below it are compared now. Columns turn green when they stay and orange when they are deleted.

Step 1: The same grid. deleted starts at 0.

Step 2: Column 0, rows 0 and 1: a then b, fine.

Step 3: Column 0, rows 1 and 2: b then r, fine.

Step 4: Column 0, rows 2 and 3: r then g goes backwards. Column 0 is deleted (deleted = 1).

Step 5: Column 1, rows 0 and 1: p then e goes backwards. Column 1 is deleted (deleted = 2), and y and u below are never read.

Step 6: Column 2, rows 0 and 1: e then e, equal, allowed.

Step 7: Column 2, rows 1 and 2: e then e, equal, allowed.

Step 8: Column 2, rows 2 and 3: e then m, fine. No step went backwards, so column 2 stays.

Step 9: Return 2, after 7 comparisons instead of 13.

1. Set deleted = 0.
2. For each column c from 0 to m − 1:
   • For each row r from 1 to n − 1: if strs[r − 1][c] > strs[r][c], add 1 to deleted and break out to the next column.
3. Return deleted.

The break matters. Column 1 of Example 1, p, e, y, u, goes backwards twice, at p → e and at y → u. Without the break it would be counted twice, and the answer would come out as 3 instead of 2. A column is deleted once, however many backwards steps it has.

Use >, not >=. Equal letters are allowed. With >=, column 2 of Example 1 (e, e, e, m) would be deleted by mistake.

A single row needs no special case. With n = 1 the inner loop never runs and the answer is 0, which is right: one letter is always in order.

Time Complexity: O(n · m). Each column costs at most n − 1 comparisons and often far fewer; on random letters, about 1.7. On the full-size grid with every column sorted it makes 1,000 × 99 = 99,000 comparisons, against 4,950,000 for the pair check.

Space Complexity: O(1). A counter and two loop indexes; nothing is copied.

No method can do better in the worst case. Take a grid of at least two rows in which every letter is b. Every column is sorted, so the answer is 0. Suppose some method skipped one of its letters. That letter might instead have been an a, if it is below the top row (earlier than the b above it), or a c, if it is in the top row (later than the b below it). Either change makes its column unsorted and the answer 1. Having never looked, the method gives the same answer for both grids, so it is wrong on one of them. So on that grid every one of the n × m letters has to be read: O(n · m) is the least any method can do, and this approach reaches it.