Problem Statement in English

You are given an array of n strings strs, all of the same length. We may choose any deletion indices, and we delete all the characters in those indices for each string.

The remaining rows of strings should be in non-decreasing sorted order.

Return the minimum number of deletion indices we need to choose so that the remaining rows of strings are in non-decreasing sorted order.

Approach

We need to ensure consecutive rows are in sorted order.

So we can iterate column by column, checking if any column breaks the sorted order of any pair of consecutive rows that are not yet confirmed to be in sorted order.

  • If we find such a column, we increment our deletion count and move to the next column.

  • If the column does not break the order, we update our tracking array to mark which pairs of rows are now confirmed to be in sorted order.

    Note that we don’t need to revisit such pairs of rows in future columns. So that saves us time.

One implementation detail is that before we classify a column as unsorted, we need to check if that row pair is already confirmed to be sorted. If it is, we can skip checking that pair for the current column.

This is important because if we don’t do this, we might end up deleting more columns than necessary.

Solution in Python


class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs)
        m = len(strs[0])
        deleted = 0

        # sorted_rows[i] == True means strs[i] < strs[i+1] already confirmed
        sorted_rows = [False] * (n - 1)

        for col in range(m):
            # Check if this column breaks ordering
            for i in range(n - 1):
                if not sorted_rows[i] and strs[i][col] > strs[i + 1][col]:
                    deleted += 1
                    break
            else:
                # Column is safe → update sorted rows
                for i in range(n - 1):
                    if strs[i][col] < strs[i + 1][col]:
                        sorted_rows[i] = True

        return deleted

Complexity

  • Time: O(n×m)O(n \times m)
    Where n is the number of strings and m is the length of each string.

  • Space: O(n)O(n)
    We use an additional array sorted_rows of size n-1 to keep track of which rows are already confirmed to be in sorted order.

Mistakes I Made

I had to look this one up :( I overcomplicated things a lot.

And we are done.