Delete Columns to Make Sorted III solution and explanation
Google
9 more videos on this problem
Delete Columns to Make Sorted III | Hard Made Easy | Dry Run | Leetcode 960 | codestorywithMIKcodestorywithMIK · 35:32 · 6K views
Delete Columns to Make Sorted III | LeetCode 960 | Complete Intuition ExplainedSanyam IIT Guwahati · 16:18 · 912 views
960. Delete Columns to Make Sorted III | Leetcode Daily - PythonLeetcode Daily · 9:36 · 593 views
Daily Leetcode #2092: Dec 22, 2025 - 960. Delete Columns to Make Sorted IIIProgramming Live with Larry · 14:43 · 522 views
Delete Columns to Make Sorted III 🔥 | LeetCode 960 | Recursion + Memoization | DP LIS variant Study Placement · 28:13 · 435 views
LeetCode 960. Delete Columns to Make Sorted III Solution Explained - JavaAlgorithms and Data Structures Course · 14:12 · 416 views
LC. 960. Delete Columns to Make Sorted IIIBlagojce Pavleski · 3:12 · 289 views
Delete Columns to Make Sorted III | LeetCode 960 - Pythonimpoldev · 14:50 · 234 views
LeetCode 960 | Delete Columns to Make Sorted III | DP + LIS Explained | Java | HindiCode Kage · 11:56 · 158 views
Delete Columns to Make Sorted III | LeetCode 960 | Java Code | Developer CoderDeveloper Coder · 27:02 · 125 views
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 every string (row) in lexicographic order. (i.e., (strs[0][0] <= strs[0][1] <= ... <= strs[0][strs[0].length - 1]), and (strs[1][0] <= strs[1][1] <= ... <= strs[1][strs[1].length - 1]), and so on). Return the minimum possible value of answer.length.
Example 1:
Input: strs = ["babca","bbazb"] Output: 3 Explanation: After deleting columns 0, 1, and 4, the final array is strs = ["bc", "az"]. Both these rows are individually in lexicographic order (ie. strs[0][0] <= strs[0][1] and strs[1][0] <= strs[1][1]). Note that strs[0] > strs[1] - the array strs is not necessarily in lexicographic order.
Example 2:
Input: strs = ["edcba"] Output: 4 Explanation: If we delete less than 4 columns, the only row will not be lexicographically sorted.
Example 3:
Input: strs = ["ghi","def","abc"] Output: 0 Explanation: All rows are already lexicographically sorted.
Constraints:
n == strs.length1 <= n <= 1001 <= strs[i].length <= 100strs[i]consists of lowercase English letters.
Approach overview
Problem Overview: You are given an array of equal-length strings. Each column represents characters from all rows at the same index. The goal is to delete the minimum number of columns so that every row becomes lexicographically non‑decreasing from left to right.
The key observation: after deletions, the remaining columns must form a sequence where every row stays sorted. Instead of directly deciding which columns to remove, treat it as finding the longest valid sequence of columns that keeps all rows sorted. The answer is total columns minus that sequence length.
Approach 1: Dynamic Programming (Column LIS) (Time: O(m² * n), Space: O(m))
This is the standard optimal approach. Treat each column like an element in a Longest Increasing Subsequence problem. Let dp[j] represent the maximum number of valid columns ending at column j. For every pair of columns i < j, check whether column i can appear before column j. This requires verifying that for every row r, strs[r][i] <= strs[r][j]. If the condition holds for all rows, update dp[j] = max(dp[j], dp[i] + 1). The longest valid subsequence across columns gives the maximum columns we can keep. The minimum deletions become m - max(dp). This method leverages Dynamic Programming and works well because column count is usually small enough for the quadratic comparison.
Approach 2: Greedy with Column Comparison (Time: O(m² * n), Space: O(1))
This strategy incrementally builds a set of kept columns. For each new column, compare it with previously kept columns to verify whether adding it preserves lexicographic order across every row. The algorithm iterates through rows and checks character ordering for each candidate pair of columns. If any row violates the order, that column must be skipped (effectively deleted). While conceptually simple, repeated column comparisons can still lead to quadratic checks over columns. It relies heavily on character comparisons within the String structure and column traversal through the Array of strings.
Recommended for interviews: The dynamic programming formulation is what most interviewers expect. Recognizing that the problem reduces to a longest increasing subsequence across columns demonstrates strong problem decomposition. The greedy comparison approach helps build intuition but doesn’t clearly express the optimal subsequence structure. Showing both ideas — brute reasoning followed by the DP optimization — signals solid algorithmic thinking.
Approach 1: Dynamic Programming Approach
This approach utilizes dynamic programming to identify the minimum columns to delete to make each row lexicographically sorted. The key idea is to use a dp array where dp[j] represents the length of the longest increasing subsequence of columns ending at index j.
We'll iterate over each column and compare with the previous columns to update the dp array by checking each row for their lexicographic order. We finally return the total number of columns minus the maximum value in the dp array, which gives the least number of deletions needed.
def minDeletionSize(strs):
n = len(strs[0])
dp = [1] * n
for j in range(1, n):
for i in range(j):
if all(s[i] <= s[j] for s in strs):
dp[j] = max(dp[j], dp[i]+1)
return n - max(dp)import java.util.*;
public class Solution {
public int minDeletionSize(String[] strs) {
int n = strs[0].length();
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int j = 1; j < n; ++j) {
for (int i = 0; i < j; ++i) {
boolean valid = true;
for (String s : strs) {
if (s.charAt(i) > s.charAt(j)) {
valid = false;
break;
}
}
if (valid) dp[j] = Math.max(dp[j], dp[i] + 1);
}
}
return n - Arrays.stream(dp).max().orElse(1);
}
}#include <vector>
#include <string>
using namespace std;
int minDeletionSize(vector<string>& strs) {
int n = strs[0].size();
vector<int> dp(n, 1);
for (int j = 1; j < n; ++j) {
for (int i = 0; i < j; ++i) {
bool valid = true;
for (const auto& s : strs) {
if (s[i] > s[j]) {
valid = false;
break;
}
}
if (valid) {
dp[j] = max(dp[j], dp[i] + 1);
}
}
}
return n - *max_element(dp.begin(), dp.end());
}var minDeletionSize = function(strs) {
const n = strs[0].length;
const dp = Array(n).fill(1);
for (let j = 1; j < n; ++j) {
for (let i = 0; i < j; ++i) {
if (strs.every(s => s[i] <= s[j])) {
dp[j] = Math.max(dp[j], dp[i] + 1);
}
}
}
return n - Math.max(...dp);
};#include <stdio.h>
#include <string.h>
int minDeletionSize(char** strs, int strsSize) {
int n = strlen(strs[0]);
int dp[n];
for (int i = 0; i < n; ++i) dp[i] = 1;
for (int j = 1; j < n; ++j) {
for (int i = 0; i < j; ++i) {
int valid = 1;
for (int k = 0; k < strsSize; ++k) {
if (strs[k][i] > strs[k][j]) {
valid = 0;
break;
}
}
if (valid) {
dp[j] = fmax(dp[j], dp[i] + 1);
}
}
}
int maxLen = 0;
for (int i = 0; i < n; ++i) {
if (dp[i] > maxLen) maxLen = dp[i];
}
return n - maxLen;
}using System;
public class Solution {
public int MinDeletionSize(string[] strs) {
int n = strs[0].Length;
int[] dp = new int[n];
Array.Fill(dp, 1);
for (int j = 1; j < n; ++j) {
for (int i = 0; i < j; ++i) {
bool valid = true;
foreach (var s in strs) {
if (s[i] > s[j]) {
valid = false;
break;
}
}
if (valid) dp[j] = Math.Max(dp[j], dp[i] + 1);
}
}
return n - dp.Max();
}
}The Python implementation also uses dynamic programming, iterating over column indices to form a sequence that maintains row order. If columns i and j maintain lexicographic order across strings, the dp array element is updated. The final answer is the total column count less the longest valid sequence's length.
Time Complexity: O(n^2 * m), with n columns and m strings.
Space Complexity: O(n) for the dp list.
Approach 2: Greedy Approach with Column Comparison
This approach involves a greedy strategy where we incrementally build the sorted subset of columns. By comparing columns, we find those that necessarily break the order when removed and only retain these to maintain row order.
At each step, the algorithm compares characters in successive columns, choosing deletions based on maintaining an overall least sequence of lexicographically ordered characters per row.
def minDeletionSize(strs):
n = len(strs[0])
ans = 0
for j in range(n):
for i in range(1, len(strs)):
if strs[i][j] < strs[i - 1][j]:
ans += 1
break
return anspublic int minDeletionSize(String[] strs) {
int n = strs[0].length();
int ans = 0;
for (int j = 0; j < n; ++j) {
for (int i = 1; i < strs.length; ++i) {
if (strs[i].charAt(j) < strs[i - 1].charAt(j)) {
++ans;
break;
}
}
}
return ans;
}#include <vector>
#include <string>
using namespace std;
int minDeletionSize(vector<string>& strs) {
int n = strs[0].size();
int ans = 0;
for (int j = 0; j < n; ++j) {
for (int i = 1; i < strs.size(); ++i) {
if (strs[i][j] < strs[i - 1][j]) {
++ans;
break;
}
}
}
return ans;
}var minDeletionSize = function(strs) {
let n = strs[0].length;
let ans = 0;
for (let j = 0; j < n; ++j) {
for (let i = 1; i < strs.length; ++i) {
if (strs[i][j] < strs[i - 1][j]) {
ans++;
break;
}
}
}
return ans;
};#include <stdbool.h>
#include <string.h>
int minDeletionSize(char ** strs, int strsSize) {
int n = strlen(strs[0]);
int ans = 0;
for (int j = 0; j < n; ++j) {
bool shouldDelete = false;
for (int i = 1; i < strsSize; ++i) {
if (strs[i][j] < strs[i - 1][j]) {
shouldDelete = true;
break;
}
}
if (shouldDelete) {
ans++;
}
}
return ans;
}public class Solution {
public int MinDeletionSize(string[] strs) {
int n = strs[0].Length;
int ans = 0;
for (int j = 0; j < n; ++j) {
for (int i = 1; i < strs.Length; ++i) {
if (strs[i][j] < strs[i - 1][j]) {
++ans;
break;
}
}
}
return ans;
}
}Python also implements this through a direct comparison of each matrix column, iterating strings pairwise. When finding a non-lexical order among columns, the deletions counter increases.
Time Complexity: O(n * m), as it traverses all column elements.
Space Complexity: O(1), utilizing fixed additional space.
Approach 3: Dynamic Programming
We define f[i] as the length of the longest non-decreasing subsequence ending at column i. Initially, f[i] = 1, and the final answer is n - max(f).
To compute f[i], we iterate over all j < i. If for all strings s, we have s[j] leq s[i], then we update f[i] as follows:
$ f[i] = max(f[i], f[j] + 1)
Finally, we return n - max(f).
The time complexity is O(n^2 times m), and the space complexity is O(n), where n is the length of each string in the array strs, and m$ is the number of strings in the array.
function minDeletionSize(strs: string[]): number {
const n = strs[0].length;
const f: number[] = Array(n).fill(1);
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
let ok = true;
for (const s of strs) {
if (s[j] > s[i]) {
ok = false;
break;
}
}
if (ok) {
f[i] = Math.max(f[i], f[j] + 1);
}
}
}
return n - Math.max(...f);
}func minDeletionSize(strs []string) int {
n := len(strs[0])
f := make([]int, n)
for i := range f {
f[i] = 1
}
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
ok := true
for _, s := range strs {
if s[j] > s[i] {
ok = false
break
}
}
if ok {
f[i] = max(f[i], f[j]+1)
}
}
}
return n - slices.Max(f)
}impl Solution {
pub fn min_deletion_size(strs: Vec<String>) -> i32 {
let n = strs[0].len();
let mut f = vec![1; n];
for i in 1..n {
for j in 0..i {
if strs.iter().all(|s| s.as_bytes()[j] <= s.as_bytes()[i]) {
f[i] = f[i].max(f[j] + 1);
}
}
}
(n - *f.iter().max().unwrap()) as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2 * m), with n columns and m strings. |
| Greedy Approach with Column Comparison | Time Complexity: O(n * m), as it traverses all column elements. |
| Dynamic Programming | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Column LIS) | O(m² * n) | O(m) | General case and interview settings where optimal subsequence detection is required |
| Greedy Column Comparison | O(m² * n) | O(1) | Conceptual approach for understanding column ordering without maintaining DP state |
Frequently asked questions
Is Delete Columns to Make Sorted III easy or hard?
Delete Columns to Make Sorted III is classified as a Hard problem because the correct insight requires transforming the problem into a longest increasing subsequence across columns while validating ordering across multiple rows.
Delete Columns to Make Sorted III Python/Java solution
Python, Java, C++, and JavaScript implementations typically use the same DP idea: maintain a dp array for column subsequence length and update it by checking every earlier column. The result is total columns minus the longest valid subsequence.
How to solve Delete Columns to Make Sorted III in O(n)?
A strict O(n) solution is not feasible because column relationships must be validated across rows. The best known approach is O(m^2 * n) using dynamic programming to compute the longest valid sequence of columns that preserves lexicographic order.
What is the best approach for Delete Columns to Make Sorted III?
The most effective solution uses dynamic programming similar to the Longest Increasing Subsequence (LIS). Each column is treated as a candidate in the sequence, and two columns are compatible if every row keeps lexicographic order between them. This produces an O(m^2 * n) time solution with O(m) space.
Is Delete Columns to Make Sorted III asked at Google/Amazon/Meta?
Variants of column deletion and lexicographic ordering problems appear in interviews at large tech companies including Google, Amazon, and Meta. The problem tests dynamic programming reasoning and the ability to transform constraints into a subsequence optimization.
What data structure is used in Delete Columns to Make Sorted III?
The solution mainly relies on arrays for storing the input strings and a dynamic programming array to track the longest valid column sequence. Character comparisons within strings determine whether two columns can coexist in the sorted order.
What is the time complexity of Delete Columns to Make Sorted III?
The optimal dynamic programming solution runs in O(m^2 * n) time, where m is the number of columns and n is the number of rows. Every pair of columns may be compared, and each comparison checks all rows. Space complexity is O(m) for the DP array.