944. Delete Columns to Make Sorted
Model: qwen2.5-coder:14b
Topics: Greedy
FAANG asked: 1
Acceptance rate: 70.9%
Problem Breakdown
The problem requires us to determine the number of columns in a grid formed by an array of strings that are not sorted lexicographically. Each string in the array has the same length. We need to delete these unsorted columns and return the count of such deletions.
Inputs:
- An array of
nstrings, where each string has the same length. - The number of strings
nranges from 1 to 100. - Each string’s length can range from 1 to 1000.
- Strings consist only of lowercase English letters.
Outputs:
- An integer representing the number of columns that need to be deleted.
Implicit Constraints or Tricky Edge Cases:
- If there is only one string, all columns are trivially sorted.
- If all strings are identical, no columns will need to be deleted.
- The grid can be very large (up to 100,000 characters per column), so the solution should be efficient in terms of both time and space.
Intuition
A brute-force approach would involve checking each column individually to see if it is sorted. This would have a time complexity of O(n * m^2), where n is the number of strings and m is the length of each string, which could be inefficient given the constraints.
The key insight is to recognize that we can check each column in linear time by iterating through the characters of each string in the column. If any character is less than the previous one, the column is not sorted, and we should count it for deletion.
Approach
- Initialize a counter
delete_countto zero. - Iterate over each column index from 0 to
m-1. - For each column, iterate through each string in the array starting from the second string.
- Compare the current character with the previous one in the same column.
- If any character is less than the previous one, increment the
delete_countand break out of the inner loop to move to the next column. - Return the
delete_count.
Complexity Analysis
- Time Complexity: O(n * m), where
nis the number of strings andmis the length of each string. We iterate through each character in the grid once. - Space Complexity: O(1). We only use a constant amount of extra space for the counter.
Solution
def minDeletionSize(strs):
delete_count = 0
m = len(strs[0]) # Number of columns
for col in range(m):
for row in range(1, len(strs)):
if strs[row][col] < strs[row - 1][col]:
delete_count += 1
break
return delete_count
Edge Cases Handled
- Single String: If there is only one string, the loop will not execute, and
delete_countremains zero. - All Identical Strings: All columns will be sorted, so
delete_countremains zero. - Large Grids: The solution efficiently handles large grids by iterating through each character in the grid once.