LeetCode 944: Delete Columns to Make Sorted

Problem Restatement

We are given an array of equal-length strings:

strs

Think of the strings as rows of a character matrix.

We may delete some columns.

A column is valid if its characters are in non-decreasing order from top to bottom.

For a column c, we need:

strs[0][c] <= strs[1][c] <= strs[2][c] <= ...

Return the minimum number of columns that must be deleted so that every remaining column is sorted.

The official statement defines the same column-ordering rule and asks for the minimum number of deleted columns. (leetcode.com)

Input and Output

Function shape:

class Solution:
    def minDeletionSize(self, strs: list[str]) -> int:
        ...

Examples

Example 1:

strs = ["cba", "daf", "ghi"]

Check each column.

Column 0:

c, d, g

Sorted.

Column 1:

b, a, h

Not sorted because:

b > a

Delete this column.

Column 2:

a, f, i

Sorted.

Only one column must be deleted.

Answer:

1

Example 2:

strs = ["a", "b"]

The only column is:

a, b

Already sorted.

Answer:

0

Example 3:

strs = ["zyx", "wvu", "tsr"]

Every column decreases.

All columns must be deleted.

Answer:

3

These are the official examples for the problem. (github.com)

First Thought

Each column is independent.

Whether one column is sorted does not affect another column.

So we can process columns one at a time.

For each column:

1. Scan rows from top to bottom.
2. If any adjacent pair decreases, the column must be deleted.

Key Insight

We only need to compare neighboring rows.

A column is sorted if:

strs[row][col] <= strs[row + 1][col]

for every adjacent pair of rows.

The moment we find:

strs[row][col] > strs[row + 1][col]

the column is invalid.

So we can stop checking that column immediately.

Algorithm

Let:

rows = len(strs)
cols = len(strs[0])

Initialize:

deletions = 0

For every column col:

1. Check all adjacent row pairs.
2. If any pair is decreasing:
   • increase deletions
   • stop checking this column

Return deletions.

Walkthrough

Use:

strs = ["cba", "daf", "ghi"]

Rows:

c b a
d a f
g h i

Check column 0:

c <= d <= g

Valid.

Check column 1:

b > a

Invalid.

Delete count becomes:

1

Check column 2:

a <= f <= i

Valid.

Final answer:

1

Correctness

A column is valid exactly when its characters are in non-decreasing order from top to bottom.

The algorithm checks every adjacent row pair in each column.

If it finds a pair where:

strs[row][col] > strs[row + 1][col]

then the column violates the required ordering rule and must be deleted.

If no such pair exists, then every adjacent pair is ordered correctly. By transitivity, the entire column is in non-decreasing order, so the column can remain.

The algorithm processes every column independently and counts exactly the columns that violate the ordering rule.

Therefore, the returned count is the minimum number of columns that must be deleted.

Complexity

Let:

m = len(strs)
n = len(strs[0])

Implementation

class Solution:
    def minDeletionSize(self, strs: list[str]) -> int:
        rows = len(strs)
        cols = len(strs[0])

        deletions = 0

        for col in range(cols):
            for row in range(rows - 1):
                if strs[row][col] > strs[row + 1][col]:
                    deletions += 1
                    break

        return deletions

Code Explanation

We first compute the matrix dimensions:

rows = len(strs)
cols = len(strs[0])

Then we check every column:

for col in range(cols):

Inside the column, compare neighboring rows:

if strs[row][col] > strs[row + 1][col]:

If the order decreases, the column is invalid:

deletions += 1

Then:

break

because one violation is enough to require deleting the whole column.

Finally:

return deletions

Testing

def run_tests():
    s = Solution()

    assert s.minDeletionSize(["cba", "daf", "ghi"]) == 1
    assert s.minDeletionSize(["a", "b"]) == 0
    assert s.minDeletionSize(["zyx", "wvu", "tsr"]) == 3

    assert s.minDeletionSize(["abc", "bce", "cae"]) == 1
    assert s.minDeletionSize(["xga", "xfb", "yfa"]) == 1
    assert s.minDeletionSize(["aaa", "aaa", "aaa"]) == 0

    print("all tests passed")

run_tests()