Delete Columns to Make Sorted II - Practice Coding Problems

Delete Columns to Make Sorted II - 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.

Input & Output

Example 1 — Basic Case

$ Input: strs = ["ca", "bb", "ac"]

› Output: 1

💡 Note: Delete column 0: "ca"→"a", "bb"→"b", "ac"→"c". Result ["a","b","c"] is sorted. Only 1 deletion needed.

Example 2 — No Deletions Needed

$ Input: strs = ["xc", "yb", "za"]

› Output: 0

💡 Note: Already lexicographically sorted: "xc" <= "yb" <= "za". No deletions needed.

Example 3 — Multiple Deletions

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

› Output: 3

💡 Note: Must delete all columns since each column is in reverse order. After deleting all, get ["","",""] which is sorted.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Array of strings with same length

Process

Delete minimum columns to achieve lexicographic order

Output

Minimum number of deletions needed

Key Takeaway

🎯 Key Insight: Once string pairs are lexicographically separated by a column, their order is permanently established

Asked in

G Google 25 f Facebook 18 a Amazon 12

The key insight is that once two strings are lexicographically separated by a column, their relative order is fixed. Best approach uses greedy column-by-column processing with pair tracking. Time: O(mn), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Column-by-Column	O(m × n)	O(n)	Process columns left to right, delete when current column would break lexicographic order
Brute Force - Try All Combinations	O(2^m × n × m)	O(m)	Try all possible deletion combinations and find minimum that keeps lexicographic order

Greedy Column-by-Column — Algorithm Steps

Initialize tracking array for string pair relationships
For each column, check if it maintains or improves lexicographic order
Delete column if it would break the order
Update tracking array when strings become properly ordered

Visualization

Tap to expand

Step-by-Step Walkthrough

Check Column

Examine current column for ordering violations

Delete if Needed

Delete column if it would break lexicographic order

Update Tracking

Mark string pairs that become properly ordered

Code -

solution.c — C

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

int solution(char strs[][101], int n, int m) {
    if (n == 0 || m == 0) return 0;
    
    bool sortedPairs[n-1];  // Track if strs[i] < strs[i+1] is established
    for (int i = 0; i < n-1; i++) sortedPairs[i] = false;
    int deletions = 0;
    
    for (int col = 0; col < m; col++) {
        // Check if keeping this column maintains lexicographic order
        bool shouldDelete = false;
        
        for (int i = 0; i < n - 1; i++) {
            if (!sortedPairs[i]) {  // Only check pairs not yet established
                if (strs[i][col] > strs[i + 1][col]) {
                    shouldDelete = true;
                    break;
                }
            }
        }
        
        if (shouldDelete) {
            deletions++;
        } else {
            // Update sortedPairs - mark pairs that become established
            for (int i = 0; i < n - 1; i++) {
                if (!sortedPairs[i] && strs[i][col] < strs[i + 1][col]) {
                    sortedPairs[i] = true;
                }
            }
        }
    }
    
    return deletions;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    char strs[100][101];
    int n = 0, m = 0;
    char *ptr = strchr(line, '"');
    while (ptr) {
        ptr++;
        char *end = strchr(ptr, '"');
        if (!end) break;
        strncpy(strs[n], ptr, end - ptr);
        strs[n][end - ptr] = '\0';
        if (m == 0) m = strlen(strs[n]);
        n++;
        ptr = strchr(end + 1, '"');
    }
    
    printf("%d\n", solution(strs, n, m));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

Process m columns, each requiring O(n) time to check all string pairs

✓ Linear Growth

Space Complexity

O(n)

Tracking array to store which string pairs are already ordered

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 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

Greedy Column-by-Column — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler