LeetCode 944 - Delete Columns to Make Sorted

The problem gives us an array of strings where every string has exactly the same length. If we place all strings vertically, character by character, the strings form a rectangular grid.

leetcodeeasyarraystring

LeetCode Problem 944

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

The problem gives us an array of strings where every string has exactly the same length. If we place all strings vertically, character by character, the strings form a rectangular grid.

For example, given:

["abc", "bce", "cae"]

the grid becomes:

abc
bce
cae

Each column is formed by taking characters from the same index across all rows. The task is to determine how many columns are not sorted in non-decreasing lexicographical order.

A column is considered sorted if, moving from top to bottom, every character is less than or equal to the character below it. In other words, for every adjacent pair of rows:

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

must hold true.

If any adjacent pair violates this ordering rule, then that column must be deleted. The final answer is the total number of such invalid columns.

The constraints are relatively small:

  • There can be at most 100 strings
  • Each string can have length up to 1000

This means the total grid size is at most:

100 * 1000 = 100,000 characters

A solution that checks every character once or a few times is completely acceptable.

Several edge cases are important:

  • A single string means every column is automatically sorted because there are no adjacent rows to compare.
  • A single-column grid still follows the same logic.
  • Duplicate characters are allowed because the ordering requirement is non-decreasing, not strictly increasing.
  • Columns can fail immediately at the first comparison, so efficient early termination inside a column check is useful.

Approaches

Brute Force Approach

The most direct way to solve the problem is to inspect every column independently.

For each column:

  1. Compare every adjacent pair of rows.
  2. If at any point the upper character is greater than the lower character, mark the column as invalid.
  3. Count how many invalid columns exist.

This approach is already efficient enough for the constraints because every cell in the grid is examined at most once.

The brute-force terminology here refers to directly simulating the problem statement without any additional optimization tricks or preprocessing.

The correctness is straightforward because the problem definition itself says a column is invalid if any adjacent pair is out of order.

Key Insight for the Optimal Solution

The important observation is that each column is completely independent from every other column.

Whether one column is sorted has no effect on any other column. Therefore, we do not need complicated data structures or sorting operations. We simply scan vertically through each column and validate its ordering.

As soon as we find one inversion in a column:

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

we already know the column must be deleted, so we can stop checking that column immediately.

This gives us a clean and efficient linear scan over the grid.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(rows × cols) O(1) Directly checks every column pairwise
Optimal O(rows × cols) O(1) Same asymptotic complexity, but stops early when a column becomes invalid

Algorithm Walkthrough

  1. Determine the number of rows and columns.

The number of rows is simply len(strs), and the number of columns is len(strs[0]) because all strings have equal length. 2. Initialize a counter for deleted columns.

This variable keeps track of how many columns violate the sorted ordering condition. 3. Iterate through each column.

For every column index col, we will validate whether the characters from top to bottom remain in non-decreasing order. 4. Compare adjacent rows within the current column.

For every row index row from 0 to rows - 2, compare:

strs[row][col]

with:

strs[row + 1][col]
  1. Detect an invalid ordering.

If:

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

then the column is not sorted lexicographically.

Increase the deletion counter and immediately stop checking the current column because one violation is enough to invalidate it. 6. Continue until all columns are processed.

After examining every column, return the total number of invalid columns.

Why it works

The algorithm works because a column is sorted if and only if every adjacent pair of characters is in non-decreasing order. By checking all adjacent row pairs in a column, we fully verify the sorting condition. If even one pair violates the ordering rule, the column must be deleted. Since every column is checked independently and exhaustively, the final count is guaranteed to be correct.

Python Solution

from typing import List

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

The implementation begins by determining the dimensions of the grid. Since all strings have equal length, the first string provides the total number of columns.

The outer loop iterates through each column independently. For every column, the inner loop compares adjacent rows from top to bottom.

The key condition is:

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

If this becomes true, the column violates lexicographical ordering and must be deleted. The deletion counter is incremented, and the break statement immediately stops further checks for that column because additional comparisons are unnecessary.

Finally, after all columns are processed, the function returns the total number of invalid columns.

Go Solution

func minDeletionSize(strs []string) int {
    rows := len(strs)
    cols := len(strs[0])

    deletions := 0

    for col := 0; col < cols; col++ {
        for row := 0; row < rows-1; row++ {
            if strs[row][col] > strs[row+1][col] {
                deletions++
                break
            }
        }
    }

    return deletions
}

The Go implementation follows the exact same logic as the Python solution.

Strings in Go can be indexed directly because the input only contains lowercase English letters, which are single-byte ASCII characters. This avoids complications related to UTF-8 multi-byte characters.

The algorithm uses constant extra memory and scans the grid column by column exactly as described earlier.

Worked Examples

Example 1

Input:

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

Grid:

cba
daf
ghi

Column 0

Row Comparison Characters Valid?
row 0 vs row 1 c <= d Yes
row 1 vs row 2 d <= g Yes

Column 0 is sorted.

Column 1

Row Comparison Characters Valid?
row 0 vs row 1 b <= a No

Column 1 is invalid.

Current deletions:

1

Column 2

Row Comparison Characters Valid?
row 0 vs row 1 a <= f Yes
row 1 vs row 2 f <= i Yes

Column 2 is sorted.

Final answer:

1

Example 2

Input:

strs = ["a","b"]

Grid:

a
b

Column 0

Row Comparison Characters Valid?
row 0 vs row 1 a <= b Yes

No invalid columns exist.

Final answer:

0

Example 3

Input:

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

Grid:

zyx
wvu
tsr

Column 0

Row Comparison Characters Valid?
row 0 vs row 1 z <= w No

Invalid column count:

1

Column 1

Row Comparison Characters Valid?
row 0 vs row 1 y <= v No

Invalid column count:

2

Column 2

Row Comparison Characters Valid?
row 0 vs row 1 x <= u No

Invalid column count:

3

Final answer:

3

Complexity Analysis

Measure Complexity Explanation
Time O(rows × cols) Every character comparison is performed at most once
Space O(1) Only a few integer variables are used

The algorithm processes each column independently and compares adjacent rows within that column. Since there are rows - 1 comparisons per column and cols columns total, the total work is proportional to the number of cells in the grid.

No additional data structures are required, so the extra memory usage remains constant.

Test Cases

from typing import List

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

solution = Solution()

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

assert solution.minDeletionSize(["a"]) == 0  # Single row
assert solution.minDeletionSize(["abc"]) == 0  # One string, all columns valid
assert solution.minDeletionSize(["aa", "aa"]) == 0  # Equal characters allowed
assert solution.minDeletionSize(["ba", "aa"]) == 1  # First column invalid
assert solution.minDeletionSize(["ab", "ac"]) == 0  # Properly sorted columns
assert solution.minDeletionSize(["rrjk", "furt", "guzm"]) == 2  # Mixed valid/invalid columns
assert solution.minDeletionSize(["x", "w", "v"]) == 1  # Single column descending
assert solution.minDeletionSize(["abc", "bcd", "cde"]) == 0  # Fully sorted grid
assert solution.minDeletionSize(["edc", "dcb", "cba"]) == 3  # Every column invalid
Test Why
["cba", "daf", "ghi"] Validates mixed valid and invalid columns
["a", "b"] Smallest non-trivial valid input
["zyx", "wvu", "tsr"] Every column invalid
["a"] Single-row edge case
["abc"] One string means all columns are valid
["aa", "aa"] Confirms equal characters are allowed
["ba", "aa"] Tests early invalid detection
["ab", "ac"] Tests properly sorted columns
["rrjk", "furt", "guzm"] Mixed ordering across multiple columns
["x", "w", "v"] Single-column descending input
["abc", "bcd", "cde"] Completely sorted grid
["edc", "dcb", "cba"] Completely unsorted grid

Edge Cases

A single-row input is an important edge case because there are no adjacent rows to compare. Every column is automatically sorted. A buggy implementation might incorrectly assume at least two rows exist and attempt invalid comparisons. This implementation handles the case naturally because the inner loop runs from 0 to rows - 2, which becomes empty when rows == 1.

Columns containing equal adjacent characters are another subtle case. The problem requires non-decreasing lexicographical order, not strictly increasing order. That means values like:

a
a
b

are completely valid. The implementation correctly uses the condition:

>

instead of:

>=

which ensures equal characters remain valid.

A fully descending column is also important because the algorithm should terminate early for efficiency. Consider:

z
a

The first comparison already proves the column is invalid. The implementation uses break immediately after detecting a violation, avoiding unnecessary comparisons and improving practical performance.