Delete Columns to Make Sorted - Practice Coding Problems

Delete Columns to Make Sorted - Problem

Array String Easy

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.

Input & Output

Example 1 — Basic Case

$ Input: strs = ["abc", "bce", "cae"]

› Output: 1

💡 Note: Column 0: 'a','b','c' is sorted. Column 1: 'b','c','a' is not sorted (c > a). Column 2: 'c','e','e' is sorted. Delete 1 column.

Example 2 — All Sorted

$ Input: strs = ["abcdef"]

› Output: 0

💡 Note: Only one string, so all columns are trivially sorted. Delete 0 columns.

Example 3 — All Unsorted

$ Input: strs = ["zyx", "wvu", "tsr"]

› Output: 3

💡 Note: All columns are in descending order. Column 0: 'z','w','t', Column 1: 'y','v','s', Column 2: 'x','u','r'. Delete all 3 columns.

Constraints

1 ≤ strs.length ≤ 100
1 ≤ strs[i].length ≤ 1000
strs[i] consists of lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings: ["abc", "bce", "cae"]

Form Grid

Arrange strings as rows to visualize columns

Check Columns

Count unsorted columns that need deletion

Key Takeaway

🎯 Key Insight: A column is sorted if characters read top-to-bottom are in non-decreasing lexicographic order

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to check each column independently for lexicographic ordering. For each column, compare adjacent characters from top to bottom - if any character is greater than the one below it, the column must be deleted. Best approach is the single pass with early termination. Time: O(n×m), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Single Pass Optimized	O(n × m)	O(1)	Check each column once with early termination
Brute Force - Check Each Column	O(n × m)	O(1)	Iterate through each column and check if characters are sorted

Single Pass Optimized — Algorithm Steps

Step 1: Iterate through each column index
Step 2: For each column, compare adjacent characters
Step 3: Use early termination when unsorted pair found
Step 4: Return total count of deleted columns

Visualization

Tap to expand

Step-by-Step Walkthrough

Column 0 Check

a ≤ b ≤ c: sorted, keep it

Column 1 Check

b ≤ c but c > a: unsorted, delete and stop checking this column

Column 2 Check

c ≤ e ≤ e: sorted, keep it

Code -

solution.c — C

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

int solution(char strs[][101], int n, int m) {
    if (n == 0 || m == 0) return 0;
    
    int deleteCount = 0;
    
    // Check each column
    for (int col = 0; col < m; col++) {
        // Check if current column is sorted
        for (int row = 1; row < n; row++) {
            if (strs[row][col] < strs[row-1][col]) {
                deleteCount++;
                break; // Early termination
            }
        }
    }
    
    return deleteCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for JSON array
    char strs[1000][101];
    int n = 0, m = 0;
    
    char* ptr = strchr(line, '"');
    while (ptr != NULL) {
        ptr++; // Skip opening quote
        int len = 0;
        while (*ptr != '"') {
            strs[n][len++] = *ptr++;
        }
        strs[n][len] = '\0';
        if (m == 0) m = len;
        n++;
        ptr = strchr(ptr + 1, '"');
        if (ptr) ptr = strchr(ptr + 1, '"'); // Skip to next opening quote
    }
    
    int result = solution(strs, n, m);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m)

In worst case, we check all characters in the grid (n rows × m columns)

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables for counting and indexing

✓ Linear Space

28.5K Views

Medium Frequency

~8 min Avg. Time

845 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Single Pass Optimized — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler