# LeetCode 944: Delete Columns to Make Sorted

## Problem Restatement

We are given an array of equal-length strings:

```python
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:

```text
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](https://leetcode.com/problems/delete-columns-to-make-sorted/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array of equal-length strings `strs` |
| Output | Minimum number of deleted columns |
| Valid column | Characters are non-decreasing top to bottom |
| Operation | Delete entire columns |

Function shape:

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

## Examples

Example 1:

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

Check each column.

Column `0`:

```text
c, d, g
```

Sorted.

Column `1`:

```text
b, a, h
```

Not sorted because:

```text
b > a
```

Delete this column.

Column `2`:

```text
a, f, i
```

Sorted.

Only one column must be deleted.

Answer:

```python
1
```

Example 2:

```python
strs = ["a", "b"]
```

The only column is:

```text
a, b
```

Already sorted.

Answer:

```python
0
```

Example 3:

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

Every column decreases.

All columns must be deleted.

Answer:

```python
3
```

These are the official examples for the problem. ([github.com](https://github.com/doocs/leetcode/blob/main/solution/0900-0999/0944.Delete%20Columns%20to%20Make%20Sorted/README_EN.md?utm_source=chatgpt.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:

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

for every adjacent pair of rows.

The moment we find:

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

the column is invalid.

So we can stop checking that column immediately.

## Algorithm

Let:

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

Initialize:

```python
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:

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

Rows:

```text
c b a
d a f
g h i
```

Check column `0`:

```text
c <= d <= g
```

Valid.

Check column `1`:

```text
b > a
```

Invalid.

Delete count becomes:

```python
1
```

Check column `2`:

```text
a <= f <= i
```

Valid.

Final answer:

```python
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:

```text
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:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(m * n)` | Each cell may be checked once |
| Space | `O(1)` | Only counters are used |

## Implementation

```python
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:

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

Then we check every column:

```python
for col in range(cols):
```

Inside the column, compare neighboring rows:

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

If the order decreases, the column is invalid:

```python
deletions += 1
```

Then:

```python
break
```

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

Finally:

```python
return deletions
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `["cba","daf","ghi"]` | Standard example |
| `["a","b"]` | Already sorted |
| `["zyx","wvu","tsr"]` | Every column invalid |
| Mixed valid and invalid columns | General behavior |
| Single decreasing position | Early stop check |
| Equal characters | Non-decreasing is allowed |