955. Delete Columns to Make Sorted II LeetCode Solution
In this guide, you will get 955. Delete Columns to Make Sorted II LeetCode Solution with the best time and space complexity. The solution to Delete Columns to Make Sorted II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Delete Columns to Make Sorted II
You are given an array of n strings strs, all of the same length.
We may choose any deletion indices, and we delete all the characters in those indices for each string.
For example, if we have strs = [“abcdef”,”uvwxyz”] and deletion indices {0, 2, 3}, then the final array after deletions is [“bef”, “vyz”].
Suppose we chose a set of deletion indices answer such that after deletions, the final array has its elements in lexicographic order (i.e., strs[0] <= strs[1] <= strs[2] <= … <= strs[n – 1]). Return the minimum possible value of answer.length.
Example 1:
Input: strs = [“ca”,”bb”,”ac”]
Output: 1
Explanation:
After deleting the first column, strs = [“a”, “b”, “c”].
Now strs is in lexicographic order (ie. strs[0] <= strs[1] <= strs[2]).
We require at least 1 deletion since initially strs was not in lexicographic order, so the answer is 1.
Input: strs = ["xc","yb","za"]
Output: 0
Explanation:
strs is already in lexicographic order, so we do not need to delete anything.
Note that the rows of strs are not necessarily in lexicographic order:
i.e., it is NOT necessarily true that (strs[0][0] <= strs[0][1] <= …)
Example 3:
Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: We have to delete every column.
Constraints:
n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 100
strs[i] consists of lowercase English letters.
Complexity Analysis
Time Complexity: O(|\texttt{strs[0]}| \cdot n)
Space Complexity: O(n)
955. Delete Columns to Make Sorted II LeetCode Solution in C++
class Solution {
public:
int minDeletionSize(vector<string>& strs) {
const int n = strs.size();
int ans = 0;
// sorted[i] := true if strs[i] < strs[i + 1]
vector<bool> sorted(n - 1);
for (int j = 0; j < strs[0].length(); ++j) {
int i;
for (i = 0; i + 1 < n; ++i)
if (!sorted[i] && strs[i][j] > strs[i + 1][j]) {
++ans;
break;
}
// Already compared each pair, so update the sorted array if needed.
if (i + 1 == n)
for (i = 0; i + 1 < n; ++i)
sorted[i] = sorted[i] || strs[i][j] < strs[i + 1][j];
}
return ans;
}
}; /* code provided by PROGIEZ */
955. Delete Columns to Make Sorted II LeetCode Solution in Java
class Solution {
public int minDeletionSize(String[] strs) {
final int n = strs.length;
int ans = 0;
// sorted[i] := true if strs[i] < strs[i + 1]
boolean[] sorted = new boolean[n - 1];
for (int j = 0; j < strs[0].length(); ++j) {
int i;
for (i = 0; i + 1 < n; ++i)
if (!sorted[i] && strs[i].charAt(j) > strs[i + 1].charAt(j)) {
++ans;
break;
}
// strslready compared each pair, so update the sorted array if needed.
if (i + 1 == n)
for (i = 0; i + 1 < n; ++i)
sorted[i] = sorted[i] || strs[i].charAt(j) < strs[i + 1].charAt(j);
}
return ans;
}
} // code provided by PROGIEZ
955. Delete Columns to Make Sorted II LeetCode Solution in Python
