Delete Columns to Make Sorted II

Medium
1461.

Delete Columns to Make Sorted II

Delete Columns to Make Sorted II is a medium coding problem on arrays, strings and greedy, asked in Amazon and Google interviews.

You are given n strings strs of equal length. You may choose a set of column indices and delete those characters from every string.

After the deletion, the strings must be in lexicographic order: strs[0] <= strs[1] <= … <= strs[n - 1].

Return the minimum number of columns to delete.

Example 1

Input
strs = ["kc","kb","za"]
Output
1
Explanation
Deleting column 1 leaves `["k","k","z"]`, which is in order.

Example 2

Input
strs = ["abx","agz","bgc","bfc"]
Output
1
Explanation
Delete column 1 to get `["ax","az","bc","bc"]`.

Example 3

Input
strs = ["zyx","wvu","tsr"]
Output
3

Constraints

  • n == strs.length
  • 1 <= n <= 100
  • 1 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string[]} strs
 * @return {number}
 */
var minDeletionSize = function(strs) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Delete Columns to Make Sorted II — Problem & Solution

Delete Columns to Make Sorted II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Delete Columns to Make Sorted II is a medium coding problem on arrays, strings and greedy, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Strings, Greedy
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given n strings strs of equal length. You may choose a set of column indices and delete those characters from every string.

After the deletion, the strings must be in lexicographic order: strs[0] <= strs[1] <= … <= strs[n - 1].

Return the minimum number of columns to delete.

Example 1

Input: strs = ["kc","kb","za"]
Output: 1
Explanation: Deleting column 1 leaves `["k","k","z"]`, which is in order.

Example 2

Input: strs = ["abx","agz","bgc","bfc"]
Output: 1
Explanation: Delete column 1 to get `["ax","az","bc","bc"]`.

Example 3

Input: strs = ["zyx","wvu","tsr"]
Output: 3

Constraints

  • n == strs.length
  • 1 <= n <= 100
  • 1 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters

Hints for Delete Columns to Make Sorted II

  1. Hint 1

    Process the columns from left to right, deciding keep or delete for each.

  2. Hint 2

    Once two neighbouring strings differ (strictly) in a kept column, their order is settled and later columns cannot break it.

  3. Hint 3

    Delete a column if it puts some still-unsettled neighbouring pair out of order; otherwise keep it and mark the pairs it separates as settled.

How to solve Delete Columns to Make Sorted II

Lexicographic order is decided by the first kept column where two strings differ. Scan columns left to right, remembering which adjacent pairs are already strictly ordered; a column is deleted only when it would break an unresolved pair.

Approach

  1. Keep a flag settled[i] for each adjacent pair (i, i + 1), all false at first.
  2. For each column j: if some unsettled pair has strs[i][j] > strs[i + 1][j], delete the column (count it) and skip it.
  3. Otherwise keep it, and set settled[i] for every pair with strs[i][j] < strs[i + 1][j].
  4. Return the number of deleted columns.

Why it works

A column that breaks an unsettled pair must be deleted in every valid solution that keeps the earlier columns the greedy kept — keeping it would place that pair out of order for good. A column that breaks nothing can always be kept: it never hurts settled pairs and only settles more pairs, which leaves strictly more freedom for later columns. Comparing only adjacent pairs is enough, since sortedness of a list is the sortedness of its neighbours.

Complexity

  • Time — O(n · m)
  • Space — O(n)

Pitfalls

  • Unlike the first version, a column out of order for a pair that is already settled does not need deleting.
  • Decide the column first, then update the settled flags — never update flags from a deleted column.
  • Equal letters do not settle a pair; only a strict increase does.

Reference solution

Python

from typing import List

def minDeletionSize(strs: List[str]) -> int:
    n, m = len(strs), len(strs[0])
    settled = [False] * (n - 1)
    deleted = 0
    for j in range(m):
        if any(not settled[i] and strs[i][j] > strs[i + 1][j] for i in range(n - 1)):
            deleted += 1
            continue
        for i in range(n - 1):
            if strs[i][j] < strs[i + 1][j]:
                settled[i] = True
    return deleted

Java

public static int minDeletionSize(String[] strs) {
    int n = strs.length, m = strs[0].length();
    boolean[] settled = new boolean[n];
    int deleted = 0;
    for (int j = 0; j < m; j++) {
        boolean bad = false;
        for (int i = 0; i + 1 < n; i++) {
            if (!settled[i] && strs[i].charAt(j) > strs[i + 1].charAt(j)) { bad = true; break; }
        }
        if (bad) { deleted++; continue; }
        for (int i = 0; i + 1 < n; i++) if (strs[i].charAt(j) < strs[i + 1].charAt(j)) settled[i] = true;
    }
    return deleted;
}

C++

int minDeletionSize(vector<string>& strs) {
    int n = strs.size(), m = strs[0].size();
    vector<bool> settled(n, false);
    int deleted = 0;
    for (int j = 0; j < m; j++) {
        bool bad = false;
        for (int i = 0; i + 1 < n; i++) {
            if (!settled[i] && strs[i][j] > strs[i + 1][j]) { bad = true; break; }
        }
        if (bad) { deleted++; continue; }
        for (int i = 0; i + 1 < n; i++) if (strs[i][j] < strs[i + 1][j]) settled[i] = true;
    }
    return deleted;
}

JavaScript

var minDeletionSize = function(strs) {
    var n = strs.length, m = strs[0].length;
    var settled = new Array(n).fill(false);
    var deleted = 0;
    for (var j = 0; j < m; j++) {
        var bad = false;
        for (var i = 0; i + 1 < n; i++) {
            if (!settled[i] && strs[i][j] > strs[i + 1][j]) { bad = true; break; }
        }
        if (bad) { deleted++; continue; }
        for (var t = 0; t + 1 < n; t++) if (strs[t][j] < strs[t + 1][j]) settled[t] = true;
    }
    return deleted;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings