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.length1 <= n <= 1001 <= strs[i].length <= 100strs[i] consists of lowercase English letters
Hints for Delete Columns to Make Sorted II
Hint 1
Process the columns from left to right, deciding keep or delete for each.
Hint 2
Once two neighbouring strings differ (strictly) in a kept column, their order is settled and later columns cannot break it.
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
- Keep a flag
settled[i]for each adjacent pair(i, i + 1), all false at first. - For each column
j: if some unsettled pair hasstrs[i][j] > strs[i + 1][j], delete the column (count it) and skip it. - Otherwise keep it, and set
settled[i]for every pair withstrs[i][j] < strs[i + 1][j]. - 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 deletedJava
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.