#955

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Delete Columns to Make Sorted II

Solve the "Delete Columns to Make Sorted II" problem by applying greedy choices and invariant validation to string arrays.

array string greedy

Problem Statement

You are given an array of n strings of the same length. The goal is to delete specific columns to make the array lexicographically sorted, where a column deletion removes that character from every string in the array.

For example, in strs = ["abcdef","uvwxyz"] with deletion indices {0, 2, 3}, the final result would be ["bef", "vyz"]. Your task is to determine the minimum number of columns to delete to achieve lexicographic order across the strings.

Examples

Example 1

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

Output: 1

After deleting the first column, strs = ["a", "b", "c"]. Now strs is in lexicographic order (ie. strs[0] <= strs[1] <= strs[2]). We require at least 1 deletion since initially strs was not in lexicographic order, so the answer is 1.

Example 2

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

Output: 0

strs is already in lexicographic order, so we do not need to delete anything. Note that the rows of strs are not necessarily in lexicographic order: i.e., it is NOT necessarily true that (strs[0][0] <= strs[0][1] <= ...)

Example 3

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

Output: 3

We have to delete every column.

Constraints

n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.

Solution Approach

Greedy Column Deletion

Use a greedy approach by iterating through columns and ensuring the lexicographic order is preserved across all rows. Deleting columns as needed minimizes deletions, ensuring the array remains sorted.

Invariant Validation

Validate the sorted invariant while processing each column. If deleting a column maintains or improves the order, it should be removed. This check ensures minimal deletions for the desired outcome.

Efficient Column Comparison

After processing each column, compare the current string against the previous one. If the current column disrupts the order, it should be deleted. This approach leverages the row-by-row comparison to detect the minimum deletions.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the approach to checking each column and comparing rows, typically O(n * m), where n is the number of strings and m is the length of each string. Space complexity is usually O(1), but may vary based on the approach used to track deleted columns.

What Interviewers Usually Probe

Candidate demonstrates a clear understanding of greedy algorithms and invariant validation.
Candidate is able to identify when and why column deletions are necessary based on lexicographic order.
Candidate can efficiently walk through each column and validate the condition without unnecessary recomputations.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check lexicographic order after each column deletion, leading to unnecessary deletions.
Confusing this problem with problems that require sorting entire rows, rather than focusing on column deletions.
Not considering edge cases like an already sorted array or cases where no deletions are needed.

Follow-up variants

Consider a variant where the strings are of varying lengths but still require lexicographic ordering.
A version where deletions can be performed at the row level instead of the column level, altering the complexity.
A variation where you are given a set of allowed deletions and need to minimize them to maintain the order.

FAQ

What is the primary strategy for solving the "Delete Columns to Make Sorted II" problem?

The primary strategy is to use a greedy approach with invariant validation, ensuring the lexicographic order is maintained by deleting columns when necessary.

How do we decide which columns to delete in the "Delete Columns to Make Sorted II" problem?

We delete columns if their characters disrupt the lexicographic order across rows. This ensures minimal deletions while maintaining the desired order.

Can this problem be solved with dynamic programming?

While dynamic programming is not the optimal solution for this problem, it could be adapted. The greedy approach combined with invariant validation is more efficient.

What is the time complexity of the "Delete Columns to Make Sorted II" problem?

The time complexity is O(n * m), where n is the number of strings and m is the length of each string, as we check each column and compare rows.

What is the best way to handle edge cases in "Delete Columns to Make Sorted II"?

Edge cases like already sorted arrays or arrays with no required deletions should be handled early in the algorithm to avoid unnecessary computations.

terminal

Solution

Solution 1: Greedy

When comparing strings in lexicographical order, we compare from left to right, and the first unequal character determines the ordering relationship between two strings. Therefore, we can traverse each column from left to right and determine whether the current column needs to be deleted.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def minDeletionSize(self, strs: List[str]) -> int:
        n = len(strs)
        m = len(strs[0])
        st = [False] * (n - 1)
        ans = 0
        for j in range(m):
            must_del = False
            for i in range(n - 1):
                if not st[i] and strs[i][j] > strs[i + 1][j]:
                    must_del = True
                    break
            if must_del:
                ans += 1
            else:
                for i in range(n - 1):
                    if not st[i] and strs[i][j] < strs[i + 1][j]:
                        st[i] = True
        return ans

Continue Practicing

#942 di string match #1578 minimum time to make rope colorful #179 largest number