Leetcode 955: Delete Columns to Make Sorted II
You are given an array of strings, where each string is of the same length. You are allowed to delete any number of columns, and after deleting the selected columns, the remaining strings should be in lexicographically non-decreasing order. Your task is to determine the minimum number of columns that must be deleted to achieve this order.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of n strings, each string having the same length.
Example: Input: strs = ["ab","ac","bb"]
Constraints:
• 1 <= strs.length <= 100
• 1 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.
Output: The output should be an integer representing the minimum number of columns that need to be deleted to make the array of strings lexicographically ordered.
Example: Output: 1
Constraints:
• The output is an integer.
Goal: The goal is to minimize the number of columns that need to be deleted while ensuring the remaining strings are in lexicographically non-decreasing order.
Steps:
• 1. Initialize a counter to track the number of deletions.
• 2. Traverse through each column and check if the current column violates the lexicographical order between adjacent strings.
• 3. If a violation is found, increment the deletion counter and skip further checks for that column.
• 4. After checking each column, return the counter as the minimum number of deletions required.
Goal: The array will have at least one string and can have up to 100 strings, with each string being at most 100 characters long.
Steps:
• The input will always have strings of the same length.
• The number of strings will be between 1 and 100.
• The length of each string will be between 1 and 100.
• All characters in the strings are lowercase English letters.
Assumptions:
• All input strings are valid and consist only of lowercase English letters.
• The length of all strings is the same.
• Input: Input: strs = ["ab","ac","bb"]
• Explanation: In this case, deleting the second column (index 1) results in the array ["a", "c", "b"], which is lexicographically ordered.
• Input: Input: strs = ["dc","ba","za"]
• Explanation: In this case, no deletions are required since the array is already in lexicographic order.
• Input: Input: strs = ["zyx","wvu","tsr"]
• Explanation: Here, all columns violate the lexicographic order, so all columns must be deleted, resulting in an answer of 3.
Approach: We approach this problem by checking each column for lexicographical violations between adjacent rows. If a column violates the order, we count it as a column to delete.
Observations:
• The problem is primarily about identifying columns that cause lexicographical violations.
• We need to check each column for lexicographical order violations and count how many columns need to be deleted.
Steps:
• 1. Initialize a variable to track the number of columns to delete.
• 2. Loop through each column of the strings and compare adjacent strings to check if they are in lexicographical order.
• 3. If a violation is found in a column, increment the deletion count and skip further checks for that column.
• 4. Once all columns are processed, return the deletion count as the result.
Empty Inputs:
• The input will always have at least one string, so no need to handle empty inputs.
Large Inputs:
• For large inputs with 100 strings and each string having 100 characters, the algorithm should efficiently process the array within the time limits.
Special Values:
• The strings may contain identical characters, but the logic still applies for detecting lexicographical violations.
Constraints:
• Ensure the solution handles arrays with up to 100 strings and strings of length up to 100 characters efficiently.
int minDeletionSize(vector<string>& strs) {
int res = 0, m = strs.size(), n = strs[0].size();
int i , j;
vector<bool> sorted(m - 1, false);
for(j = 0; j < n; j++) {
for(i = 0; i < m - 1; i++) {
if(!sorted[i] && strs[i][j] > strs[i + 1][j]) {
res++;
break;
}
}
if(i < m - 1) continue;
for(i = 0; i < m - 1; i++) {
sorted[i] = sorted[i] || strs[i][j] < strs[i + 1][j];
}
}
return res;
}
1 : Function Declaration
int minDeletionSize(vector<string>& strs) {
Function declaration for `minDeletionSize` which takes a vector of strings as input and returns an integer result.
2 : Variable Initialization
int res = 0, m = strs.size(), n = strs[0].size();
Initialize variables: `res` to track the number of deletions, `m` for the number of rows, and `n` for the number of columns.
3 : Loop Variables
int i , j;
Declare loop variables `i` and `j` to iterate over rows and columns respectively.
4 : Sorted Vector
vector<bool> sorted(m - 1, false);
Initialize a boolean vector `sorted` of size `m-1` to track which adjacent rows are already sorted.
5 : Outer Loop
for(j = 0; j < n; j++) {
Iterate through each column in the strings using the outer loop variable `j`.
6 : Inner Loop
for(i = 0; i < m - 1; i++) {
Inner loop to check adjacent rows for sorting in the current column.
7 : Check Condition
if(!sorted[i] && strs[i][j] > strs[i + 1][j]) {
Check if the current column violates the sorting order for adjacent rows that are not already sorted.
8 : Increment Result
res++;
If the current column violates sorting, increment the deletion count `res`.
9 : Break
break;
Exit the inner loop early if a deletion is determined for the current column.
10 : Skip Current Column
if(i < m - 1) continue;
If the column is marked for deletion, skip further processing for it.
11 : Update Sorted
for(i = 0; i < m - 1; i++) {
Update the `sorted` state for adjacent rows based on the current column.
12 : Update Condition
sorted[i] = sorted[i] || strs[i][j] < strs[i + 1][j];
Mark adjacent rows as sorted if the current column satisfies the sorting condition.
13 : Return Result
return res;
Return the total number of columns that need to be deleted to make rows sorted.
Best Case: O(n * m)
Average Case: O(n * m)
Worst Case: O(n * m)
Description: 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 check each column for each string.
Best Case: O(1)
Worst Case: O(1)
Description: The space complexity is O(1) since we only need a constant amount of extra space for tracking deletions.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus