Delete Columns to Make Sorted solution and explanation
Google
9 more videos on this problem
Delete Columns to Make Sorted | MICROSOFT | Leetcode 944 | codestorywithMIKcodestorywithMIK · 6:56 · 12K views
944. Delete Columns to Make Sorted (Leetcode Easy)Programming Live with Larry · 6:07 · 917 views
944. Delete Columns to Make Sorted | Leetcode Daily - PythonLeetcode Daily · 9:31 · 306 views
LeetCode 944 | Delete Columns to Make Sorted | Streak 🔥| JAVACoding Spark · 10:22 · 245 views
Leetcode | Easy | 944 | Delete Columns to Make Sorted | Java SolutionCode Monger · 5:51 · 212 views
944. Delete columns to make sorted | LeetcodeA Code Daily! · 11:51 · 191 views
Leetcode 944: Delete Columns to Make SortedAlgorithms Casts · 6:23 · 155 views
Delete Columns to Make Sorted on Leetcode || Q. 944 || Easy Explanation || Implementation in PythonCodeRapt · 7:16 · 137 views
Leetcode 944 Delete Columns to Make Sorted - C++ Solution [English]Mohamed Hamada (Hamada) · 9:08 · 127 views
Leetcode | 944 Delete Columns to Make Sorted | Java | Simple Appraoch | Daily ChallengeCakot Coding · 6:27 · 112 views
The problem
You are given an array of n strings strs, all of the same length.
The strings can be arranged such that there is one on each line, making a grid.
- For example,
strs = ["abc", "bce", "cae"]can be arranged as follows:
abc bce cae
You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e') are sorted, while column 1 ('b', 'c', 'a') is not, so you would delete column 1.
Return the number of columns that you will delete.
Example 1:
Input: strs = ["cba","daf","ghi"] Output: 1 Explanation: The grid looks as follows: cba daf ghi Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.
Example 2:
Input: strs = ["a","b"] Output: 0 Explanation: The grid looks as follows: a b Column 0 is the only column and is sorted, so you will not delete any columns.
Example 3:
Input: strs = ["zyx","wvu","tsr"] Output: 3 Explanation: The grid looks as follows: zyx wvu tsr All 3 columns are not sorted, so you will delete all 3.
Constraints:
n == strs.length1 <= n <= 1001 <= strs[i].length <= 1000strs[i]consists of lowercase English letters.
Approach overview
Problem Overview: You get an array of equal-length strings. Each column is formed by taking characters at the same index from every string. The task is to count how many columns must be deleted so that every remaining column is lexicographically sorted from top to bottom.
Approach 1: Brute Force, Column-wise Check (Time: O(n * m), Space: O(1))
Iterate column by column and verify whether the characters in that column are sorted across all rows. For column j, compare adjacent rows strs[i][j] and strs[i+1][j]. If any pair violates lexicographic order (i.e., strs[i][j] > strs[i+1][j]), the column must be deleted. Continue this check for every column and count the violations.
This approach treats each column independently and performs a full scan across rows every time. No extra data structures are required since comparisons happen directly on characters inside the strings. The algorithm relies on simple iteration over a 2D grid of characters, making it easy to implement using basic array traversal and string indexing.
Approach 2: Optimized Single Pass Check (Time: O(n * m), Space: O(1))
The optimized version follows the same column-wise traversal but exits early as soon as a violation is detected. While scanning column j, the moment strs[i][j] > strs[i+1][j] appears, the column is marked for deletion and the loop breaks immediately. This avoids unnecessary comparisons for the rest of that column.
The key idea is recognizing that one violation is enough to invalidate the column. Early termination reduces the constant factor in practice, especially when unsorted columns appear frequently. You still iterate across all columns, but many columns stop scanning after only a few comparisons.
This approach still uses simple character comparisons and sequential traversal, which keeps memory usage constant. It works well for typical interview constraints where the number of rows and columns can both be moderately large.
Recommended for interviews: The optimized single-pass check is what interviewers expect. It shows that you recognize the independence of each column and apply an early break when a violation appears. Starting with the brute-force explanation demonstrates clear reasoning, while the optimized version shows attention to efficiency and clean iteration over arrays of strings.
Approach 1: Approach 1: Brute Force, Column-wise Check
This approach involves iterating over each column in the grid formed by the strings. For each column, we compare the characters from top to bottom to ensure that they are in non-decreasing order. If a column is found to be unsorted, it needs to be deleted. We maintain a count of such unsorted columns and return this count at the end.
def minDeletionSize(strs):
del_count = 0
for col in range(len(strs[0])):
for row in range(1, len(strs)):
if strs[row][col] < strs[row - 1][col]:
del_count += 1
break
return del_count
# Example Usage
strs = ["cba", "daf", "ghi"]
print(minDeletionSize(strs))public class Solution {
public int minDeletionSize(String[] strs) {
int delCount = 0;
int columnCount = strs[0].length();
for (int col = 0; col < columnCount; col++) {
for (int row = 1; row < strs.length; row++) {
if (strs[row].charAt(col) < strs[row - 1].charAt(col)) {
delCount++;
break;
}
}
}
return delCount;
}
public static void main(String[] args) {
Solution sol = new Solution();
String[] strs = {"cba", "daf", "ghi"};
System.out.println(sol.minDeletionSize(strs));
}
}#include <vector>
#include <string>
#include <iostream>
int minDeletionSize(std::vector<std::string>& strs) {
int delCount = 0;
int columnCount = strs[0].size();
for (int col = 0; col < columnCount; ++col) {
for (int row = 1; row < strs.size(); ++row) {
if (strs[row][col] < strs[row - 1][col]) {
delCount++;
break;
}
}
}
return delCount;
}
int main() {
std::vector<std::string> strs = {"cba", "daf", "ghi"};
std::cout << minDeletionSize(strs) << std::endl;
return 0;
}function minDeletionSize(strs) {
let delCount = 0;
const columnCount = strs[0].length;
for (let col = 0; col < columnCount; col++) {
for (let row = 1; row < strs.length; row++) {
if (strs[row][col] < strs[row - 1][col]) {
delCount++;
break;
}
}
}
return delCount;
}
// Example Usage
let strs = ["cba", "daf", "ghi"];
console.log(minDeletionSize(strs));#include <stdio.h>
#include <string.h>
int minDeletionSize(char **strs, int strsSize) {
int delCount = 0;
int columnCount = strlen(strs[0]);
for (int col = 0; col < columnCount; col++) {
for (int row = 1; row < strsSize; row++) {
if (strs[row][col] < strs[row - 1][col]) {
delCount++;
break;
}
}
}
return delCount;
}
int main() {
char *strs[] = {"cba", "daf", "ghi"};
int size = sizeof(strs) / sizeof(strs[0]);
printf("%d\n", minDeletionSize(strs, size));
return 0;
}using System;
public class Solution {
public int MinDeletionSize(string[] strs) {
int delCount = 0;
int columnCount = strs[0].Length;
for (int col = 0; col < columnCount; col++) {
for (int row = 1; row < strs.Length; row++) {
if (strs[row][col] < strs[row - 1][col]) {
delCount++;
break;
}
}
}
return delCount;
}
public static void Main(string[] args) {
string[] strs = {"cba", "daf", "ghi"};
Solution sol = new Solution();
Console.WriteLine(sol.MinDeletionSize(strs));
}
}The Python solution checks each column character by character. If a column is unsorted (i.e., any character is less than its above character), we increase the deletion count and move to the next column.
Time Complexity: O(m * n)
Space Complexity: O(1)
Approach 2: Approach 2: Optimized Single Pass Check
In this approach, instead of checking each column individually with a nested loop, we try to reduce the checks by using internal helper functions or flags. This might reduce the overhead for checking conditions multiple times, though generally both approaches might occupy similar time complexity due to the input constraints.
def minDeletionSize(strs):
del_count = 0
for col in range(len(strs[0])):
if not all(strs[row][col] >= strs[row - 1][col] for row in range(1, len(strs))):
del_count += 1
return del_count
# Example Usage
strs = ["cba", "daf", "ghi"]
print(minDeletionSize(strs))public class Solution {
public int minDeletionSize(String[] strs) {
int delCount = 0;
int columnCount = strs[0].length();
for (int col = 0; col < columnCount; col++) {
boolean sorted = true;
for (int row = 1; row < strs.length && sorted; row++) {
if (strs[row].charAt(col) < strs[row - 1].charAt(col)) {
delCount++;
sorted = false;
}
}
}
return delCount;
}
public static void main(String[] args) {
Solution sol = new Solution();
String[] strs = {"cba", "daf", "ghi"};
System.out.println(sol.minDeletionSize(strs));
}
}#include <vector>
#include <string>
#include <iostream>
int minDeletionSize(std::vector<std::string>& strs) {
int delCount = 0;
int columnCount = strs[0].size();
for (int col = 0; col < columnCount; ++col) {
bool sorted = true;
for (int row = 1; row < strs.size() && sorted; ++row) {
if (strs[row][col] < strs[row - 1][col]) {
delCount++;
sorted = false;
}
}
}
return delCount;
}
int main() {
std::vector<std::string> strs = {"cba", "daf", "ghi"};
std::cout << minDeletionSize(strs) << std::endl;
return 0;
}function minDeletionSize(strs) {
let delCount = 0;
const columnCount = strs[0].length;
for (let col = 0; col < columnCount; col++) {
let sorted = true;
for (let row = 1; row < strs.length && sorted; row++) {
if (strs[row][col] < strs[row - 1][col]) {
delCount++;
sorted = false;
}
}
}
return delCount;
}
// Example Usage
let strs = ["cba", "daf", "ghi"];
console.log(minDeletionSize(strs));#include <stdio.h>
#include <stdbool.h>
int minDeletionSize(char **strs, int strsSize) {
int delCount = 0;
int columnCount = strlen(strs[0]);
for (int col = 0; col < columnCount; col++) {
bool isValid = true;
for (int row = 1; row < strsSize && isValid; row++) {
if (strs[row][col] < strs[row - 1][col]) {
delCount++;
isValid = false;
}
}
}
return delCount;
}
int main() {
char *strs[] = {"cba", "daf", "ghi"};
int size = sizeof(strs) / sizeof(strs[0]);
printf("%d\n", minDeletionSize(strs, size));
return 0;
}using System;
public class Solution {
public int MinDeletionSize(string[] strs) {
int delCount = 0;
int columnCount = strs[0].Length;
for (int col = 0; col < columnCount; col++) {
bool sorted = true;
for (int row = 1; row < strs.Length && sorted; row++) {
if (strs[row][col] < strs[row - 1][col]) {
delCount++;
sorted = false;
}
}
}
return delCount;
}
public static void Main(string[] args) {
string[] strs = {"cba", "daf", "ghi"};
Solution sol = new Solution();
Console.WriteLine(sol.MinDeletionSize(strs));
}
}In Python, an optimization is done using a list comprehension combined with 'all' to swiftly determine if the column is valid before adding it into the deletion count.
Time Complexity: O(m * n)
Space Complexity: O(1)
Approach 3: Compare Column by Column
We denote the number of rows in the string array strs as n, and the number of columns as m.
We traverse each column, starting from the second row, and compare the character of the current row with that of the previous row column by column. If the character of the current row is less than that of the previous row, it indicates that the current column is not arranged in non-strictly increasing lexicographical order, and we need to delete it, incrementing the result by one, then break out of the inner loop.
Finally, we return the result.
The time complexity is O(L), where L is the total length of the strings in the array strs. The space complexity is O(1).
function minDeletionSize(strs: string[]): number {
const [m, n] = [strs[0].length, strs.length];
let ans = 0;
for (let j = 0; j < m; ++j) {
for (let i = 1; i < n; ++i) {
if (strs[i][j] < strs[i - 1][j]) {
++ans;
break;
}
}
}
return ans;
}func minDeletionSize(strs []string) (ans int) {
m, n := len(strs[0]), len(strs)
for j := 0; j < m; j++ {
for i := 1; i < n; i++ {
if strs[i][j] < strs[i-1][j] {
ans++
break
}
}
}
return
}impl Solution {
pub fn min_deletion_size(strs: Vec<String>) -> i32 {
let n = strs.len();
let m = strs[0].len();
let mut ans = 0;
for j in 0..m {
for i in 1..n {
if strs[i].as_bytes()[j] < strs[i - 1].as_bytes()[j] {
ans += 1;
break;
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force, Column-wise Check | Time Complexity: O(m * n) Space Complexity: O(1) |
| Approach 2: Optimized Single Pass Check | Time Complexity: O(m * n) Space Complexity: O(1) |
| Compare Column by Column | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force, Column-wise Check | O(n * m) | O(1) | Good for understanding the problem. Simple full scan of each column. |
| Optimized Single Pass Check | O(n * m) | O(1) | Preferred in interviews. Stops scanning a column immediately after detecting an order violation. |
Frequently asked questions
Is Delete Columns to Make Sorted easy or hard?
Delete Columns to Make Sorted is categorized as an Easy problem on LeetCode with a high acceptance rate. The logic mainly involves nested iteration and lexicographic comparison of characters across rows.
Delete Columns to Make Sorted Python/Java solution
In both Python and Java, the implementation iterates through columns first and rows second. For each column j, compare strs[i][j] with strs[i+1][j]. If a violation occurs, increment the deletion counter and break out of the inner loop.
How to solve Delete Columns to Make Sorted in O(n)?
A strict O(n) solution is not possible because every column must be inspected. The optimal approach is O(n * m), where you iterate through each column and compare characters across rows. Early termination inside a column reduces unnecessary comparisons but does not change the asymptotic complexity.
What is the best approach for Delete Columns to Make Sorted?
The best approach is a column-wise traversal with an early break when a lexicographic violation is found. For each column j, compare adjacent rows using strs[i][j] and strs[i+1][j]. If any pair is out of order, increment the delete count and move to the next column. This runs in O(n * m) time with O(1) space.
Is Delete Columns to Make Sorted asked at Google/Amazon/Meta?
This problem represents a common pattern used in coding interviews at companies like Google, Amazon, and Meta. While the exact question may vary, column-wise validation and string comparison problems frequently appear in interview rounds.
What data structure is used in Delete Columns to Make Sorted?
The solution primarily uses arrays of strings. Characters are accessed using string indexing, and comparisons are performed directly between adjacent rows. No additional data structures like hash maps or stacks are required.
What is the time complexity of Delete Columns to Make Sorted?
The time complexity is O(n * m), where n is the number of strings and m is the length of each string. Each column is checked and may require scanning all adjacent row pairs. Space complexity remains O(1) because the algorithm only uses a few counters.