955. Delete Columns to Make Sorted II - Solution

Q: Is Delete Columns to Make Sorted II easy or hard?

Delete Columns to Make Sorted II is rated Medium difficulty. The challenge is recognizing that lexicographic order depends only on the first differing column and that resolved row pairs never need to be checked again. Once this observation is made, the greedy O(m*n) solution becomes straightforward.

Q: How to solve Delete Columns to Make Sorted II in O(n)?

The problem can be solved in O(m*n) time using a greedy column scan. Maintain a boolean array tracking row pairs already sorted. For each column, check unresolved pairs; if any pair violates lexicographic order, delete the column. Otherwise update the pairs that become strictly ordered after this column.

Q: Delete Columns to Make Sorted II Python or Java solution?

Both Python and Java implementations follow the same greedy idea: iterate column by column, check violations among unresolved row pairs, and update a boolean array when pairs become sorted. The algorithm structure remains identical across Python, Java, C++, C#, and JavaScript.

Q: What is the best approach for Delete Columns to Make Sorted II?

The greedy column validation approach is the most efficient solution. Scan columns from left to right and track which adjacent rows are already lexicographically ordered. If a column violates ordering for any unresolved pair, delete it; otherwise mark pairs that become sorted. This runs in O(m*n) time and O(m) space, where m is the number of rows and n is the number of columns.

Q: Is Delete Columns to Make Sorted II asked at Google/Amazon/Meta?

String ordering and greedy validation problems like this appear in interviews at companies such as Google, Amazon, and Meta. Variants that involve lexicographic constraints, column deletions, or maintaining sorted order are common in mid-level algorithm interviews.

Q: What data structure is used in Delete Columns to Make Sorted II?

The solution mainly uses arrays and strings. A boolean array tracks which adjacent row pairs are already confirmed sorted, and character comparisons are performed directly on the string matrix. No complex data structures are required.

Q: What is the time complexity of Delete Columns to Make Sorted II?

The optimal greedy solution runs in O(m * n) time because each column is scanned once and compared across adjacent rows. Space complexity is O(m) for tracking which row pairs are already confirmed sorted. A dynamic programming alternative takes O(n^2 * m) time due to pairwise column checks.

The problem

You are given an array of n strings strs, all of the same length.

We may choose any deletion indices, and we delete all the characters in those indices for each string.

For example, if we have strs = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef", "vyz"].

Suppose we chose a set of deletion indices answer such that after deletions, the final array has its elements in lexicographic order (i.e., strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Return the minimum possible value of answer.length.

Example 1:

Input: strs = ["ca","bb","ac"]
Output: 1
Explanation: 
After deleting the first column, strs = ["a", "b", "c"].
Now strs is in lexicographic order (ie. strs[0] <= strs[1] <= strs[2]).
We require at least 1 deletion since initially strs was not in lexicographic order, so the answer is 1.

Example 2:

Input: strs = ["xc","yb","za"]
Output: 0
Explanation: 
strs is already in lexicographic order, so we do not need to delete anything.
Note that the rows of strs are not necessarily in lexicographic order:
i.e., it is NOT necessarily true that (strs[0][0] <= strs[0][1] <= ...)

Example 3:

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: We have to delete every column.

Constraints:

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

Approach overview

Problem Overview: You are given an array of equal-length strings. You may delete any column. The goal is to remove the minimum number of columns so the rows remain lexicographically sorted from top to bottom.

Approach 1: Greedy Column Validation (O(m*n) time, O(m) space)

This approach scans columns from left to right and greedily decides whether a column must be deleted. Maintain an array sorted where sorted[i] indicates whether row i is already confirmed to be lexicographically smaller than row i+1. For each column, check every unresolved adjacent pair. If a column causes strs[i][col] > strs[i+1][col], the column must be deleted. Otherwise, update pairs that become strictly ordered. The key insight: once a pair is confirmed sorted, future columns cannot invalidate it. This prevents unnecessary comparisons and ensures each column is processed once.

The greedy rule works because lexicographic order is determined by the first differing character. If a column breaks order for an unresolved pair, keeping it would permanently violate sorting. This makes deletion the only safe choice. The algorithm iterates through array columns and performs character comparisons across rows, making it efficient even when string length grows.

Approach 2: Dynamic Programming on Columns (O(n^2 * m) time, O(n) space)

The dynamic programming view treats each column as a potential element in a valid subsequence of columns that preserves lexicographic order. Define dp[c] as the maximum number of columns that can end with column c. For every earlier column p, check whether keeping both columns maintains non-decreasing characters for every row: strs[r][p] <= strs[r][c]. If valid, update dp[c] = max(dp[c], dp[p] + 1). The longest valid column subsequence determines how many columns you can keep, and the rest must be deleted.

This approach resembles a longest increasing subsequence over columns but validated across all rows simultaneously. It relies heavily on repeated comparisons across rows of the string matrix. While conceptually clean, the quadratic column comparisons make it slower than the greedy strategy for large inputs.

Recommended for interviews: The greedy approach is the expected solution. It uses a simple observation about lexicographic ordering and avoids unnecessary checks once row pairs become fixed. The DP approach demonstrates deeper reasoning about column subsequences, but its O(n^2 * m) complexity is rarely preferred when the greedy greedy solution achieves optimal performance.

Approach 1: Greedy Approach

In this approach, we iterate through each column and check if any column violates the lexicographic order of rows. If we find such a column, we mark it for deletion. We need to ensure that any deletion does not affect previously sorted columns.

Python

def minDeletionSize(strs):
    len_str = len(strs[0])
    deletions = 0
    n = len(strs)
    is_sorted = [False] * (n - 1)

    for j in range(len_str):
        valid = True
        for i in range(n - 1):
            if not is_sorted[i] and strs[i][j] > strs[i + 1][j]:
                valid = False
                break

        if valid:
            for i in range(n - 1):
                if strs[i][j] < strs[i + 1][j]:
                    is_sorted[i] = True
        else:
            deletions += 1

    return deletions

print(minDeletionSize(["ca", "bb", "ac"]))

Java

class Solution {
    public int minDeletionSize(String[] strs) {
        int len = strs[0].length();
        int deletions = 0;
        int n = strs.length;
        boolean[] isSorted = new boolean[n];

        for (int j = 0; j < len; j++) {
            boolean valid = true;
            for (int i = 0; i < n - 1; i++) {
                if (!isSorted[i] && strs[i].charAt(j) > strs[i + 1].charAt(j)) {
                    valid = false;
                    break;
                }
            }

            if (valid) {
                for (int i = 0; i < n - 1; i++) {
                    if (strs[i].charAt(j) < strs[i + 1].charAt(j)) {
                        isSorted[i] = true;
                    }
                }
            } else {
                deletions++;
            }
        }

        return deletions;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] strs = {"ca", "bb", "ac"};
        System.out.println(solution.minDeletionSize(strs));
    }
}

C++

#include <vector>
#include <string>
#include <cstring>
#include <iostream>
using namespace std;

int minDeletionSize(vector<string>& strs) {
    int len = strs[0].size();
    int deletions = 0;
    int n = strs.size();
    vector<int> isSorted(n, 0);

    for (int j = 0; j < len; j++) {
        bool valid = true;
        for (int i = 0; i < n - 1; i++) {
            if (!isSorted[i] && strs[i][j] > strs[i + 1][j]) {
                valid = false;
                break;
            }
        }

        if (valid) {
            for (int i = 0; i < n - 1; i++) {
                if (strs[i][j] < strs[i + 1][j]) {
                    isSorted[i] = 1;
                }
            }
        } else {
            deletions++;
        }
    }

    return deletions;
}

int main() {
    vector<string> strs = {"ca", "bb", "ac"};
    cout << minDeletionSize(strs) << endl;
    return 0;
}

JavaScript

function minDeletionSize(strs) {
    let len = strs[0].length;
    let deletions = 0;
    let n = strs.length;
    let isSorted = Array(n - 1).fill(false);

    for (let j = 0; j < len; j++) {
        let valid = true;
        for (let i = 0; i < n - 1; i++) {
            if (!isSorted[i] && strs[i][j] > strs[i + 1][j]) {
                valid = false;
                break;
            }
        }

        if (valid) {
            for (let i = 0; i < n - 1; i++) {
                if (strs[i][j] < strs[i + 1][j]) {
                    isSorted[i] = true;
                }
            }
        } else {
            deletions++;
        }
    }

    return deletions;
}

console.log(minDeletionSize(["ca", "bb", "ac"]));

#include <stdio.h>
#include <string.h>

int minDeletionSize(char **strs, int strsSize) {
    int len = strlen(strs[0]);
    int deletions = 0;
    int n = strsSize;
    int isSorted[n];
    memset(isSorted, 0, sizeof(isSorted));

    for (int j = 0; j < len; j++) {
        char column[n];
        for (int i = 0; i < n; i++) {
            column[i] = strs[i][j];
        }

        int valid = 1;
        for (int i = 0; i < n - 1; i++) {
            if (!isSorted[i] && column[i] > column[i + 1]) {
                valid = 0;
                break;
            }
        }

        if (valid) {
            for (int i = 0; i < n - 1; i++) {
                if (column[i] < column[i + 1]) {
                    isSorted[i] = 1;
                }
            }
        } else {
            deletions++;
        }
    }

    return deletions;
}

int main() {
    char *strs[] = {"ca", "bb", "ac"};
    int n = 3;
    printf("%d\n", minDeletionSize(strs, n));
    return 0;
}

using System;

public class Solution {
    public int MinDeletionSize(string[] strs) {
        int len = strs[0].Length;
        int deletions = 0;
        int n = strs.Length;
        bool[] isSorted = new bool[n];

        for (int j = 0; j < len; j++) {
            bool valid = true;
            for (int i = 0; i < n - 1; i++) {
                if (!isSorted[i] && strs[i][j] > strs[i + 1][j]) {
                    valid = false;
                    break;
                }
            }

            if (valid) {
                for (int i = 0; i < n - 1; i++) {
                    if (strs[i][j] < strs[i + 1][j]) {
                        isSorted[i] = true;
                    }
                }
            } else {
                deletions++;
            }
        }

        return deletions;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();
        string[] strs = {"ca", "bb", "ac"};
        Console.WriteLine(solution.MinDeletionSize(strs));
    }
}

The Python solution efficiently checks column by column for any out-of-order characters which could disrupt lexicographic order between any two consecutive rows. It uses an array to maintain the status of sorted rows and minimize deletions for maintaining order.

Complexity

Time Complexity: O(n*m), where n is the number of strings and m is the length of each string.
Space Complexity: O(n), to track sorted rows with a boolean list.

Try this approach in the editor

Approach 2: Dynamic Programming Approach

This approach involves creating a dynamic programming table to maintain possible sequences that keep the strings sorted. We try to find and maintain the minimum deletions required while ensuring each column is evaluated with consideration to previously processed columns.

Python

def minDeletionSize(strs):
    m, n = len(strs), len(strs[0])
    dp = [float('inf')] * n

    for j in range(n):
        dp[j] = j
        for i in range(j):
            if all(x[i] <= x[j] for x in strs):
                dp[j] = min(dp[j], dp[i] + j - i - 1)

    return min(dp) + n - 1 - dp.index(min(dp))

print(minDeletionSize(["ca", "bb", "ac"]))

Java

import java.util.Arrays;

public class Solution {
    public int minDeletionSize(String[] strs) {
        int m = strs.length, n = strs[0].length();
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);

        for (int j = 0; j < n; ++j) {
            dp[j] = j;
            for (int i = 0; i < j; ++i) {
                boolean valid = true;
                for (int x = 0; x < m; ++x) {
                    if (strs[x].charAt(i) > strs[x].charAt(j)) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    dp[j] = Math.min(dp[j], dp[i] + j - i - 1);
                }
            }
        }

        int minDeletions = Integer.MAX_VALUE;
        for (int value : dp) {
            minDeletions = Math.min(minDeletions, value + n - 1 - (value == Integer.MAX_VALUE ? 0 : value));
        }
        return minDeletions;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] strs = {"ca", "bb", "ac"};
        System.out.println(solution.minDeletionSize(strs));
    }
}

C++

#include <vector>
#include <string>
#include <climits>
#include <algorithm>
#include <iostream>
using namespace std;

int minDeletionSize(vector<string>& strs) {
    int m = strs.size(), n = strs[0].size();
    vector<int> dp(n, INT_MAX);

    for (int j = 0; j < n; ++j) {
        dp[j] = j;
        for (int i = 0; i < j; ++i) {
            bool valid = true;
            for (int x = 0; x < m; ++x) {
                if (strs[x][i] > strs[x][j]) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                dp[j] = min(dp[j], dp[i] + j - i - 1);
            }
        }
    }

    return *min_element(dp.begin(), dp.end()) + n - 1 - (min_element(dp.begin(), dp.end()) - dp.begin());
}

int main() {
    vector<string> strs = {"ca", "bb", "ac"};
    cout << minDeletionSize(strs) << endl;
    return 0;
}

JavaScript

function minDeletionSize(strs) {
    let m = strs.length, n = strs[0].length;
    let dp = Array(n).fill(Infinity);

    for (let j = 0; j < n; ++j) {
        dp[j] = j;
        for (let i = 0; i < j; ++i) {
            if (strs.every(row => row[i] <= row[j])) {
                dp[j] = Math.min(dp[j], dp[i] + j - i - 1);
            }
        }
    }

    return Math.min(...dp.map((value, index) => value + n - 1 - index));
}

console.log(minDeletionSize(["ca", "bb", "ac"]));

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int minDeletionSize(char **strs, int strsSize) {
    int m = stringsSize, n = strlen(strs[0]);
    int *dp = (int*)malloc(m * sizeof(int));
    for (int i = 0; i < m; i++) {
        dp[i] = i;
    }

    for (int j = 1; j < n; j++) {
        for (int i = 0; i < j; i++) {
            int valid = 1;
            for (int x = 0; x < m; x++) {
                if (strs[x][i] > strs[x][j]) {
                    valid = 0;
                    break;
                }
            }
            if (valid) {
                dp[j] = dp[j] < dp[i] ? dp[j] : dp[i] + j - i - 1;
            }
        }
    }

    int res = dp[n - 1];
    for (int i = 0; i < n; i++) {
        res = res < dp[i] + n - i - 1 ? res : dp[i] + n - i - 1;
    }

    free(dp);
    return res;
}

int main() {
    char *strs[] = {"ca", "bb", "ac"};
    int n = 3;
    printf("%d\n", minDeletionSize(strs, n));
    return 0;
}

using System;

public class Solution {
    public int MinDeletionSize(string[] strs) {
        int m = strs.Length, n = strs[0].Length;
        int[] dp = new int[n];
        Array.Fill(dp, int.MaxValue);

        for (int j = 0; j < n; ++j) {
            dp[j] = j;
            for (int i = 0; i < j; ++i) {
                bool valid = true;
                for (int x = 0; x < m; ++x) {
                    if (strs[x][i] > strs[x][j]) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    dp[j] = Math.Min(dp[j], dp[i] + j - i - 1);
                }
            }
        }

        int minDeletions = int.MaxValue;
        foreach (var value in dp) {
            minDeletions = Math.Min(minDeletions, value + n - 1);
        }
        return minDeletions;
    }

    public static void Main() {
        Solution solution = new Solution();
        string[] strs = {"ca", "bb", "ac"};
        Console.WriteLine(solution.MinDeletionSize(strs));
    }
}

The Python implementation utilizes a dynamic programming matrix `dp` to hold intermediary deletions count, checking each column pair for ordered transition. Mathematic computations minimize deletions while maintaining sequence order.

Complexity

Time Complexity: O(m*n^2), where m is the number of strings and n is the length of each string.
Space Complexity: O(n), utilizing a dynamic list for column comparison results.

Try this approach in the editor

Approach 3: Greedy

When comparing strings in lexicographical order, we compare from left to right, and the first unequal character determines the ordering relationship between two strings. Therefore, we can traverse each column from left to right and determine whether the current column needs to be deleted.

We maintain a boolean array st of length n - 1, indicating whether the ordering relationship between adjacent string pairs has been determined. If the ordering relationship has been determined, then any subsequent character comparison between these two strings will not change their ordering relationship.

For each column j, we traverse all adjacent string pairs (strs[i], strs[i + 1]):

If st[i] is false and strs[i][j] > strs[i + 1][j], it means the current column must be deleted. We increment the answer by one and skip processing this column;
Otherwise, if st[i] is false and strs[i][j] < strs[i + 1][j], it means the current column determines the ordering relationship between these two strings. We set st[i] to true.

After traversing all columns, the answer is the number of columns that need to be deleted.

This greedy strategy is optimal because lexicographical order is determined by the first different column from left to right. If the current column is not deleted and causes incorrect ordering for some string pair, then regardless of subsequent columns, this error cannot be corrected, so the current column must be deleted. If the current column is not deleted and does not cause incorrect ordering for any string pair, then keeping the current column will not affect the final lexicographical ordering relationship.

The time complexity is O(n times m) and the space complexity is O(n), where n and m are the length of the string array and the length of each string, respectively.

TypeScript

function minDeletionSize(strs: string[]): number {
    const n = strs.length;
    const m = strs[0].length;
    const st: boolean[] = Array(n - 1).fill(false);
    let ans = 0;

    for (let j = 0; j < m; j++) {
        let mustDel = false;
        for (let i = 0; i < n - 1; i++) {
            if (!st[i] && strs[i][j] > strs[i + 1][j]) {
                mustDel = true;
                break;
            }
        }
        if (mustDel) {
            ans++;
        } else {
            for (let i = 0; i < n - 1; i++) {
                if (!st[i] && strs[i][j] < strs[i + 1][j]) {
                    st[i] = true;
                }
            }
        }
    }

    return ans;
}

func minDeletionSize(strs []string) int {
	n := len(strs)
	m := len(strs[0])
	st := make([]bool, n-1)
	ans := 0
	for j := 0; j < m; j++ {
		mustDel := false
		for i := 0; i < n-1; i++ {
			if !st[i] && strs[i][j] > strs[i+1][j] {
				mustDel = true
				break
			}
		}
		if mustDel {
			ans++
		} else {
			for i := 0; i < n-1; i++ {
				if !st[i] && strs[i][j] < strs[i+1][j] {
					st[i] = true
				}
			}
		}
	}
	return ans
}

Rust

impl Solution {
    pub fn min_deletion_size(strs: Vec<String>) -> i32 {
        let n = strs.len();
        let m = strs[0].len();
        let mut st = vec![false; n - 1];
        let mut ans = 0;

        for j in 0..m {
            let mut must_del = false;
            for i in 0..n - 1 {
                if !st[i] && strs[i].as_bytes()[j] > strs[i + 1].as_bytes()[j] {
                    must_del = true;
                    break;
                }
            }
            if must_del {
                ans += 1;
            } else {
                for i in 0..n - 1 {
                    if !st[i] && strs[i].as_bytes()[j] < strs[i + 1].as_bytes()[j] {
                        st[i] = true;
                    }
                }
            }
        }

        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Greedy Approach	Time Complexity: O(n*m), where n is the number of strings and m is the length of each string. Space Complexity: O(n), to track sorted rows with a boolean list.
Dynamic Programming Approach	Time Complexity: O(m*n^2), where m is the number of strings and n is the length of each string. Space Complexity: O(n), utilizing a dynamic list for column comparison results.
Greedy	–

Complexity analysis

Approach	Time	Space	When to Use
Greedy Column Validation	O(m * n)	O(m)	Best general solution; efficient for large column counts
Dynamic Programming on Columns	O(n^2 * m)	O(n)	Useful for understanding column subsequence formulation

Frequently asked questions

Is Delete Columns to Make Sorted II easy or hard?

Delete Columns to Make Sorted II is rated Medium difficulty. The challenge is recognizing that lexicographic order depends only on the first differing column and that resolved row pairs never need to be checked again. Once this observation is made, the greedy O(m*n) solution becomes straightforward.

How to solve Delete Columns to Make Sorted II in O(n)?

The problem can be solved in O(m*n) time using a greedy column scan. Maintain a boolean array tracking row pairs already sorted. For each column, check unresolved pairs; if any pair violates lexicographic order, delete the column. Otherwise update the pairs that become strictly ordered after this column.

Delete Columns to Make Sorted II Python or Java solution?

Both Python and Java implementations follow the same greedy idea: iterate column by column, check violations among unresolved row pairs, and update a boolean array when pairs become sorted. The algorithm structure remains identical across Python, Java, C++, C#, and JavaScript.

What is the best approach for Delete Columns to Make Sorted II?

The greedy column validation approach is the most efficient solution. Scan columns from left to right and track which adjacent rows are already lexicographically ordered. If a column violates ordering for any unresolved pair, delete it; otherwise mark pairs that become sorted. This runs in O(m*n) time and O(m) space, where m is the number of rows and n is the number of columns.

Is Delete Columns to Make Sorted II asked at Google/Amazon/Meta?

String ordering and greedy validation problems like this appear in interviews at companies such as Google, Amazon, and Meta. Variants that involve lexicographic constraints, column deletions, or maintaining sorted order are common in mid-level algorithm interviews.

What data structure is used in Delete Columns to Make Sorted II?

The solution mainly uses arrays and strings. A boolean array tracks which adjacent row pairs are already confirmed sorted, and character comparisons are performed directly on the string matrix. No complex data structures are required.

What is the time complexity of Delete Columns to Make Sorted II?

The optimal greedy solution runs in O(m * n) time because each column is scanned once and compared across adjacent rows. Space complexity is O(m) for tracking which row pairs are already confirmed sorted. A dynamic programming alternative takes O(n^2 * m) time due to pairwise column checks.

Delete Columns to Make Sorted II solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Dynamic Programming Approach

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Delete Columns to Make Sorted II solution and explanation

The problem

Approach overview

Approach 1: Greedy Approach

Approach 2: Dynamic Programming Approach

Approach 3: Greedy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems