Domain 2MediumMEDIUM

Delete Columns to Make Sorted II

LeetCode problem 955: Delete Columns to Make Sorted II (medium).

Domain: medium•Updated: 2026-09-04
#Greedy

Problem Breakdown

We are given an array of n strings (strs) where every string has the same length. We need to remove a minimum number of columns (character indices) such that the resulting rows form a lexicographically non-decreasing sequence (strs[0]≤strs[1]≤...strs[0] \le strs[1] \le ...).

Key Constraints & Inputs:

  • Input: List of strings strs, all same length. n=len(strs)n = len(strs), m=len(strs[i])m = len(strs[i]).
  • Output: Integer representing minimum deletions.
  • Implicit Constraint: Lexicographical comparison stops at the first differing character. If prefixes are identical up to a point, subsequent characters determine order for that specific pair of rows.

Tricky Edge Cases:

  1. Already Sorted: No columns need deletion (Output: 0).
  2. Single Row (n=1n=1): Always sorted regardless of content (Loop over pairs won’t execute).
  3. Identical Rows: If strs[i]==strs[i+1]strs[i] == strs[i+1] initially, they remain tied until a difference is found or the end.
  4. Strictly Decreasing Columns: Every column must be deleted if it violates order for any currently “tied” pair of rows.

Intuition

A brute-force approach would try all 2m2^m subsets of columns to delete, which is exponential and infeasible (O(2100)O(2^{100})). We need a greedy strategy that processes column by column from left to right.

Key Insight: Lexicographical order between two adjacent rows depends on the first column where they differ. If row ii and row i+1i+1 have been identical in all kept columns so far, we are currently “tied” for this pair.

  • Tie State: We track which pairs (i,i+1)(i, i+1) are still effectively equal based on previous kept columns using a boolean array is_less. Initially, all False (all tied).
  • Decision Rule: For the current column:
    • If any currently “tied” pair has strs[i][col]>strs[i+1][col]strs[i][col] > strs[i+1][col], this column breaks the sorted order for that specific pair. Since we cannot fix a violation in future columns (lexicographical comparison is determined by earlier differences), we must delete this entire column to avoid an invalid state.
    • If strs[i][col]<strs[i+1][col]strs[i][col] < strs[i+1][col] and they were tied, the order for that pair is now established (ii comes before i+1i+1). We mark them as resolved (is_less = True) so we stop checking this specific pair in future columns.
    • If equal, they remain tied (False), requiring further checks on subsequent columns.

Approach

We iterate through each column index from left to right (00 to m−1m-1). We maintain a state array is_less of size n−1n-1, initialized to False. This tracks which adjacent rows have already established strict order based on previously kept columns.

For every column:

  1. Check for Violations: Iterate through all pairs (i,i+1)(i, i+1) where !is_less[i]. If we find any pair where strs[i][col]>strs[i+1][col]strs[i][col] > strs[i+1][col], this column is invalid and must be deleted (ans += 1). We skip updating the state because the column doesn’t exist in the final array.
  2. Update State: If no violations are found (column kept), iterate through all pairs again where !is_less[i]. If strs[i][col]<strs[i+1][col]strs[i][col] < strs[i+1][col], mark this pair as resolved (is_less[i] = True). Pairs with equal characters remain tied.

Finally, return the total count of deleted columns.

Complexity Analysis

  • Time Complexity: O(N⋅M)O(N \cdot M), where NN is number of strings and MM is string length. We iterate through each column once (MM) and for each column scan all adjacent pairs (N−1N-1). Given constraints N,M≤100N, M \le 100, this is roughly 10410^4 operations.
  • Space Complexity: O(N)O(N) to store the is_less boolean array.

Solution

class Solution:
    def minDeletionSize(self, strs):
        n = len(strs)
        if n <= 1:
            return 0
        
        m = len(strs[0])
        ans = 0
        # Tracks whether pair (i, i+1) is strictly ordered based on kept columns.
        # False means they are still tied/equal from previous kept columns.
        is_less = [False] * (n - 1) 
        
        for col in range(m):
            delete_col = False
            
            # Check if any currently tied pair violates order at this column
            for i in range(n - 1):
                if not is_less[i]:
                    if strs[i][col] > strs[i + 1][col]:
                        delete_col = True
                        break
            
            if delete_col:
                ans += 1
            else:
                # If column kept, update state for pairs that become strictly ordered
                for i in range(n - 1):
                    if not is_less[i] and strs[i][col] < strs[i + 1][col]:
                        is_less[i] = True
                        
        return ans

Edge Cases Handled

  • Single String (n=1n=1): The loop range(n-1) becomes empty, returning 0 immediately. Correct as a single string is always sorted.
  • Already Sorted: No column triggers the deletion condition; state updates correctly but no deletions occur. Returns 0.
  • All Tied Rows (e.g., [“a”, “b”] vs [“c”, “d”]): Logic handles transitions from tied to resolved states based on character comparison.
  • Violation in First Column: If strs[0][0]>strs[1][0]strs[0][0] > strs[1][0] for any pair, delete_col becomes True immediately, incrementing count and skipping state updates (rows remain conceptually equal).