Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Lexicographical order is decided by the first differing retained character. Once an adjacent pair of rows is ordered strictly by an earlier kept column, later columns cannot spoil it. Only pairs still equal on the kept prefix constrain the next decision.

Approach

Process columns left to right, tracking which adjacent row pairs are already strictly ordered. Delete a column if it decreases for any unresolved pair: keeping it would permanently put that pair in the wrong order. Otherwise keep it and mark newly increasing pairs as resolved. Never update pair states from a deleted column. Keeping every safe column can only resolve more pairs, so it cannot require extra deletions later; the counted deletions are therefore minimal.

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

        for c in range(cols):
            valid = True
            for r in range(1, rows):
                if not isSorted[r] and strs[r][c] < strs[r - 1][c]:
                    valid = False
                    res += 1
                    break

            if not valid:
                continue

            for r in range(1, rows):
                if strs[r][c] > strs[r - 1][c]:
                    isSorted[r] = 1

        return res

Complexity analysis

For R strings and C columns, each column compares at most R - 1 adjacent pairs, so time is O(RC). The resolved-pair array uses O(R) auxiliary space.