Code Implementation

class Solution:
    def minDeletionSize(self, strs):
        # Number of columns
        n = len(strs[0])
        # Count columns to delete
        count = 0
        for col in range(n):
            for row in range(1, len(strs)):
                if strs[row][col] < strs[row-1][col]:
                    count += 1
                    break
        return count
      

class Solution {
public:
    int minDeletionSize(vector<string>& strs) {
        int n = strs[0].size();
        int count = 0;
        for (int col = 0; col < n; ++col) {
            for (int row = 1; row < strs.size(); ++row) {
                if (strs[row][col] < strs[row-1][col]) {
                    ++count;
                    break;
                }
            }
        }
        return count;
    }
};
      

class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs[0].length();
        int count = 0;
        for (int col = 0; col < n; col++) {
            for (int row = 1; row < strs.length; row++) {
                if (strs[row].charAt(col) < strs[row-1].charAt(col)) {
                    count++;
                    break;
                }
            }
        }
        return count;
    }
}
      

var minDeletionSize = function(strs) {
    let n = strs[0].length;
    let count = 0;
    for (let col = 0; col < n; col++) {
        for (let row = 1; row < strs.length; row++) {
            if (strs[row][col] < strs[row-1][col]) {
                count++;
                break;
            }
        }
    }
    return count;
};
      

Problem Description

You are given an array strs of equal-length strings, where each string represents a row in a table of characters. Your task is to determine the minimum number of columns that must be deleted so that each remaining column is sorted in non-decreasing order (from top to bottom).

A column is considered "sorted" if, for every pair of consecutive rows, the character in the lower row is not less than the character in the row above. You must not reuse elements or rearrange rows or columns—only delete entire columns.

Constraints:

• All strings in strs have the same length.
• There is only one valid solution for each input.
• You cannot rearrange or reuse elements; you may only delete columns.

Thought Process

At first glance, the problem may seem to involve sorting or rearranging columns, but the key is that you can only delete columns, not change their order. The goal is to ensure that, in the table formed by the remaining columns, every column is sorted from top to bottom.

The brute-force approach would be to check all combinations of columns to delete, but this quickly becomes infeasible as the number of columns grows. Instead, we realize that each column can be checked independently: if any column is unsorted, we must delete it. Thus, the problem reduces to scanning each column and counting the number of columns that are not sorted.

The shift from brute-force to optimization comes from the observation that we do not need to consider column interactions—each column can be checked separately.

Solution Approach

Let’s break down the algorithm step-by-step:

1. Iterate through each column: For each column index, check if the characters from top to bottom are in non-decreasing order.
2. Check each column: For each row (except the first), compare the character in the current row and column with the character in the previous row at the same column.
3. Mark unsorted columns: If you find any character that is less than the character above it, the column is unsorted and must be deleted. Increment a counter for such columns.
4. Return the count: After checking all columns, return the total count of columns to delete.

Design Justification: We use simple loops because the problem only requires checking each column independently. No advanced data structures are needed, as lookups and comparisons are constant time.

Example Walkthrough

Sample Input:
strs = ["cba", "daf", "ghi"]

• Column 0: 'c', 'd', 'g' — 'd' >= 'c', 'g' >= 'd' ⇒ Sorted.
• Column 1: 'b', 'a', 'h' — 'a' < 'b' ⇒ Not sorted. Mark for deletion.
• Column 2: 'a', 'f', 'i' — 'f' >= 'a', 'i' >= 'f' ⇒ Sorted.

Only column 1 is unsorted. So, the answer is 1.

Time and Space Complexity

• Brute-force: Checking all subsets of columns would take exponential time, O(2^n), where n is the number of columns. This is not practical.
• Optimized Solution: We check each column independently:
  • There are n columns and m rows.
  • For each column, we check up to m-1 pairs.
  • Total time: O(n * m)
  • Space: O(1), since we just use a counter.

Summary

The key insight is that each column can be checked independently for being sorted. By iterating through each column and marking those that are not sorted, we can efficiently determine the minimum number of columns to delete. This approach is simple, direct, and leverages the constraints of the problem for an elegant solution.