You are given an array of n strings strs, all of the same length.
The strings can be arranged such that there is one on each line, making a grid.
strs = ["abc", "bce", "cae"] can be arranged as follows:abc bce cae
You want to delete the columns that are not sorted lexicographically. In the above example (0-indexed), columns 0 ('a', 'b', 'c') and 2 ('c', 'e', 'e') are sorted, while column 1 ('b', 'c', 'a') is not, so you would delete column 1.
Return the number of columns that you will delete.
Example 1:
Input: strs = ["cba","daf","ghi"] Output: 1 Explanation: 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 2:
Input: strs = ["a","b"] Output: 0 Explanation: The grid looks as follows: a b Column 0 is the only column and is sorted, so you will not delete any columns.
Example 3:
Input: strs = ["zyx","wvu","tsr"] Output: 3 Explanation: The grid looks as follows: zyx wvu tsr All 3 columns are not sorted, so you will delete all 3.
Constraints:
n == strs.length1 <= n <= 1001 <= strs[i].length <= 1000strs[i] consists of lowercase English letters.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.
We start by computing the number of columns using the length of the first string. Then, we iterate over each column, and for each column, we check if it is sorted by comparing each element with its predecessor. If a descending pair is found, we increment the deletion count and break out of the loop for that column since it's unsorted.
C++
Java
Python
C#
JavaScript
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.
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n)
Space Complexity: O(1)
| Approach | Complexity |
|---|---|
| Approach 1: Brute Force, Column-wise Check | 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. |
| Approach 2: Optimized Single Pass Check | Time Complexity: O(m * n) Space Complexity: O(1) |
Leetcode 960. Delete Columns to make sorted III • Varun Gupta • 2,740 views views
Watch 9 more video solutions →Practice Delete Columns to Make Sorted with our built-in code editor and test cases.
Practice on FleetCode