#944

Easy

LeetCode Problem Workspace

Delete Columns to Make Sorted

The 'Delete Columns to Make Sorted' problem asks to remove unsorted columns from a string array, ensuring all columns are lexicographically sorted.

array string

Problem Statement

You are given an array of n strings, all of equal length. These strings can be thought of as rows in a grid where each column corresponds to a character from the strings. Your goal is to delete all columns that are not sorted in lexicographical order from top to bottom.

For example, consider the strings ['abc', 'bce', 'cae']. The first and third columns ('a', 'b', 'c' and 'c', 'e', 'e') are sorted, but the second column ('b', 'c', 'a') is not. Therefore, you must delete the second column.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

abc bce cae

Example 2

Input: strs = ["cba","daf","ghi"]

Output: 1

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 3

Input: strs = ["a","b"]

Output: 0

The grid looks as follows: a b Column 0 is the only column and is sorted, so you will not delete any columns.

Constraints

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

Solution Approach

Iterate Through Columns

The first step is to iterate through each column of the grid and compare adjacent elements. For each column, if the characters in the column are not lexicographically sorted (i.e., an element is greater than the one below it), mark that column for deletion.

Count Columns to Delete

After iterating through all columns, count the number of columns that are marked as unsorted. This will be the final answer, which represents how many columns need to be deleted.

Edge Case Handling

Be mindful of edge cases, such as when all columns are sorted or when the grid contains only one string. These cases should not require any deletions and should return 0.

Complexity Analysis

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

The time complexity of this solution is O(n * m), where n is the number of strings and m is the length of each string. This is because you are iterating through each column for every string. The space complexity is O(1) since we only need a few variables to store temporary data such as the count of deleted columns.

What Interviewers Usually Probe

Candidates should demonstrate how to check each column independently for sorting.
Watch for handling edge cases like one-column grids or already sorted grids.
A strong candidate will optimize the solution efficiently, keeping the complexity in mind.

Common Pitfalls or Variants

Common pitfalls

Not handling edge cases like grids with a single string or already sorted columns.
Misunderstanding the requirement of comparing columns rather than rows.
Overcomplicating the solution or using excessive space when only a few variables are needed.

Follow-up variants

What if the grid contains a mix of uppercase and lowercase characters? Ensure you handle character comparison correctly.
Can the problem be solved using dynamic programming? Consider whether a DP-based solution would improve efficiency.
What if the grid size increases significantly? Would this approach scale well with large inputs?

FAQ

What is the time complexity of the 'Delete Columns to Make Sorted' 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 need to iterate through each column.

How do you handle edge cases in the 'Delete Columns to Make Sorted' problem?

Edge cases like single-row grids or already sorted columns are handled by checking if any deletions are needed at all, returning 0 if no deletions are required.

How does the array plus string pattern apply to this problem?

The problem combines both array manipulation and string comparison to identify columns that are not lexicographically sorted, requiring an array-based solution for efficient column checking.

Can dynamic programming be used to solve 'Delete Columns to Make Sorted'?

While dynamic programming could be applied, the most straightforward solution is a linear scan through columns, making dynamic programming unnecessary for this problem.

What would happen if the grid contains a mix of uppercase and lowercase letters?

The problem's solution assumes lowercase English letters, but if uppercase letters are introduced, you would need to handle case-sensitive comparisons appropriately.

terminal

Solution

Solution 1: Compare Column by Column

We denote the number of rows in the string array $\textit{strs}$ as $n$, and the number of columns as $m$.

1

2

3

4

5

6

7

8

9

10

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

Continue Practicing

#943 find the shortest superstring #942 di string match #949 largest time for given digits