Problem Description
You are given an array of strings strs, all of the same length. You want to delete the columns that are not sorted lexicographically. Return the number of columns that you will delete.
Key Insights
- Each column in the grid formed by the strings can be considered independently.
- A column is sorted if the characters in that column are in non-decreasing order from top to bottom.
- We need to iterate through each column and check if it is sorted.
- The result is the count of columns that are not sorted.
Space and Time Complexity
Time Complexity: O(n * m), where n is the number of strings and m is the length of each string.
Space Complexity: O(1), as we are not using any additional data structures that scale with input size.
Solution
To solve the problem, we will iterate through each column of the strings and check if the characters are sorted in lexicographical order. We can do this by comparing each character in the column with the character directly below it. If we find any character that is greater than the character below it, we mark that column as unsorted and increase our deletion count.