Delete Columns to Make Sorted II

medium greedy array string

Problem

You are given an array of n equal-length strings. Picture them as a grid: deleting a column removes the same character index from every string. Return the minimum number of columns to delete so that the remaining strings are in lexicographic (non-decreasing) order from top to bottom.

Inputstrs = ["ca", "bb", "ac"]

Output1

Delete column 0 ("c","b","a"), leaving ["a","b","c"] which is sorted top-to-bottom. Column 1 alone is not enough, so the answer is 1.

strs (comma-separated, equal length)

def min_deletion_size(strs):
    n = len(strs)
    sorted_pairs = [False] * (n - 1)
    deletions = 0
    for col in range(len(strs[0])):
        if any(not sorted_pairs[r] and strs[r][col] > strs[r + 1][col]
               for r in range(n - 1)):
            deletions += 1
            continue
        for r in range(n - 1):
            if strs[r][col] < strs[r + 1][col]:
                sorted_pairs[r] = True
    return deletions

function minDeletionSize(strs) {
  const n = strs.length;
  const sortedPairs = new Array(n - 1).fill(false);
  let deletions = 0;
  for (let col = 0; col < strs[0].length; col++) {
    let bad = false;
    for (let r = 0; r < n - 1; r++)
      if (!sortedPairs[r] && strs[r][col] > strs[r + 1][col]) bad = true;
    if (bad) { deletions++; continue; }
    for (let r = 0; r < n - 1; r++)
      if (strs[r][col] < strs[r + 1][col]) sortedPairs[r] = true;
  }
  return deletions;
}

class Solution {
    public int minDeletionSize(String[] strs) {
        int n = strs.length;
        boolean[] sortedPairs = new boolean[n - 1];
        int deletions = 0;
        for (int col = 0; col < strs[0].length(); col++) {
            boolean bad = false;
            for (int r = 0; r < n - 1; r++)
                if (!sortedPairs[r] && strs[r].charAt(col) > strs[r + 1].charAt(col)) bad = true;
            if (bad) { deletions++; continue; }
            for (int r = 0; r < n - 1; r++)
                if (strs[r].charAt(col) < strs[r + 1].charAt(col)) sortedPairs[r] = true;
        }
        return deletions;
    }
}

int minDeletionSize(vector<string>& strs) {
    int n = strs.size();
    vector<bool> sortedPairs(n - 1, false);
    int deletions = 0;
    for (int col = 0; col < (int)strs[0].size(); col++) {
        bool bad = false;
        for (int r = 0; r < n - 1; r++)
            if (!sortedPairs[r] && strs[r][col] > strs[r + 1][col]) bad = true;
        if (bad) { deletions++; continue; }
        for (int r = 0; r < n - 1; r++)
            if (strs[r][col] < strs[r + 1][col]) sortedPairs[r] = true;
    }
    return deletions;
}

Explanation

We scan the columns left to right and greedily decide, column by column, whether to keep it or delete it. The clever bit is remembering which adjacent row-pairs are already "settled" so later columns no longer matter for them.

The array sorted_pairs has one flag per adjacent pair of rows. Once row r is strictly less than row r+1 in some kept column, their order is locked forever and later columns can be anything — we mark sorted_pairs[r] = True.

For the current column, we look only at unsettled pairs. If any unsettled pair has strs[r][col] > strs[r+1][col], keeping this column would break the order, so we must delete it and increment deletions. Otherwise the column is safe to keep, and we settle every pair where it is strictly smaller.

Greedy works because keeping a valid column never hurts: it can only settle more pairs and leave more freedom for later columns. We only delete when forced.

Example: strs=["ca","bb","ac"]. Column 0 gives the rows c, b, a which go downward — out of order — so we delete it (count 1). Column 1 gives a, b, c, which is sorted, so the answer is 1.

Time: O(n · k) Space: O(n)