Delete Columns to Make Sorted

easy string grid greedy

Problem

You are given an array of n strings, all of the same length. Imagine them written as a grid, one string per row. A column is "unsorted" if reading it top to bottom is not in non-decreasing lexicographic order. Return the number of columns you must delete so that every remaining column is sorted.

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

Output1

Column 0 is c,d,g (sorted) and column 2 is a,f,i (sorted), but column 1 is b,a,h which has a<b — so 1 column must be deleted.

strs (comma-separated, equal length)

def min_deletion_size(strs):
    rows, cols = len(strs), len(strs[0])
    deletions = 0
    for c in range(cols):
        for r in range(1, rows):
            if strs[r][c] < strs[r - 1][c]:
                deletions += 1
                break
    return deletions

function minDeletionSize(strs) {
  const rows = strs.length, cols = strs[0].length;
  let deletions = 0;
  for (let c = 0; c < cols; c++) {
    for (let r = 1; r < rows; r++) {
      if (strs[r][c] < strs[r - 1][c]) {
        deletions++;
        break;
      }
    }
  }
  return deletions;
}

class Solution {
    public int minDeletionSize(String[] strs) {
        int rows = strs.length, cols = strs[0].length();
        int deletions = 0;
        for (int c = 0; c < cols; c++) {
            for (int r = 1; r < rows; r++) {
                if (strs[r].charAt(c) < strs[r - 1].charAt(c)) {
                    deletions++;
                    break;
                }
            }
        }
        return deletions;
    }
}

int minDeletionSize(vector<string>& strs) {
    int rows = strs.size(), cols = strs[0].size();
    int deletions = 0;
    for (int c = 0; c < cols; c++) {
        for (int r = 1; r < rows; r++) {
            if (strs[r][c] < strs[r - 1][c]) {
                deletions++;
                break;
            }
        }
    }
    return deletions;
}

Explanation

Picture the strings stacked as a grid, one per row. A column is bad if, reading it top to bottom, the letters are not in non-decreasing order. We simply count how many columns are bad — that count is the number of deletions.

For each column c, we walk down the rows and compare each cell with the one directly above it. If we ever find strs[r][c] < strs[r-1][c], the column is out of order, so we add one to deletions and break out — there is no need to check the rest of that column.

This works because a column counts as a deletion the moment any single pair is out of order; one violation is enough.

Example: strs = ["cba", "daf", "ghi"]. Column 0 is c,d,g (rising, good); column 1 is b,a,h where a < b (bad, +1); column 2 is a,f,i (rising, good). So the answer is 1.

We look at each cell at most once, so the work is proportional to the grid size, rows times columns.

Time: O(rows × cols) Space: O(1)