Delete Columns to Make Sorted

Share

Given array of strings, find minimum columns to delete such that each remaining column is sorted lexicographically.

Example 1
Input: strs=["cba","daf","ghi"] → Output: 1. Delete column 0 (c,d,g is sorted, column 1 b,a,f is not).
Example 2
Input: strs=["a","b"] → Output: 0

Solution Approach

For each column index, check if column values are non-decreasing. Count unsorted columns.

  • For each column j (0 to len-1)
  • Compare strs[i][j] and strs[i+1][j] for all rows
  • If any pair is decreasing, this column must be deleted
  • Increment count and break to next column
Java
public int minDeletionSize(String[] strs) {
    int count = 0;
    for (int j = 0; j < strs[0].length(); j++) {
        for (int i = 0; i + 1 < strs.length; i++) {
            if (strs[i].charAt(j) > strs[i+1].charAt(j)) {
                count++;
                break;
            }
        }
    }
    return count;
}
  • Time Complexity: O(n*m)
  • Space Complexity: O(1)