Sponsored
Sponsored
This approach involves iterating over each column in the grid formed by the strings. For each column, we compare the characters from top to bottom to ensure that they are in non-decreasing order. If a column is found to be unsorted, it needs to be deleted. We maintain a count of such unsorted columns and return this count at the end.
Time Complexity: O(m * n), where m is the number of strings and n is the length of each string. We iterate over each column and each row within the column.
Space Complexity: O(1), no additional space is used except for a few variables.
1def minDeletionSize(strs):
2 del_count = 0
3 for col in range(len(strs[0])):
4 for row in range(1, len(strs)):
5 if strs[row][col] < strs[row - 1][col]:
6 del_count += 1
7 break
8 return del_count
9
10# Example Usage
11strs = ["cba", "daf", "ghi"]
12print(minDeletionSize(strs))The Python solution checks each column character by character. If a column is unsorted (i.e., any character is less than its above character), we increase the deletion count and move to the next column.
In this approach, instead of checking each column individually with a nested loop, we try to reduce the checks by using internal helper functions or flags. This might reduce the overhead for checking conditions multiple times, though generally both approaches might occupy similar time complexity due to the input constraints.
Time Complexity: O(m * n)
Space Complexity: O(1)
1
This C implementation checks each column with the help of a boolean flag to optimize the escape from the nested loop once an unsorted column is detected, reducing unnecessary further checks for that column.