Algorithm
Problem Name: 944. Delete Columns to Make Sorted
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.
- For example,
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.
Code Examples
#1 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int minDeletionSize(String[] A) {
int numRows = A.length;
int numCols = A[0].length();
int numDeletions = 0;
for (int i = 0; i < numCols; i++) {
for (int j = 1; j < numRows; j++) {
if (A[j].charAt(i) < A[j - 1].charAt(i)) {
numDeletions++;
break;
}
}
}
return numDeletions;
}
}
Input
#2 Code Example with Javascript Programming
Code -
Javascript Programming
const minDeletionSize = function(A) {
// increment this if we find a
// column that is out of order
let numColumnsToDelete = 0;
// all strings in the array
// are the same length
const strLength = A[0].length;
// outer loop checks entire string
for (let i = 0; i < strLength; i++) {
// inner loop checks the colunns
for (let j = 0; j < A.length - 1; j++) {
const top = A[j][i];
const bottom = A[j + 1][i];
if (top > bottom) {
numColumnsToDelete++;
break;
}
}
}
return numColumnsToDelete;
};
Input
#3 Code Example with Python Programming
Code -
Python Programming
class Solution:
def minDeletionSize(self, A):
return sum(any(a[j] > b[j] for a, b in zip(A, A[1:])) for j in range(len(A[0])))
Input
Output
#4 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _0944_DeleteColumnsToMakeSorted
{
public int MinDeletionSize(string[] A)
{
var row = A.Length;
var col = A[0].Length;
var count = 0;
for (int i = 0; i < col; i++)
{
var current_ch = A[0][i];
for (int j = 1; j < row; j++)
{
var ch = A[j][i];
if (ch < current_ch)
{
count++;
break;
}
current_ch = ch;
}
}
return count;
}
}
}
Input
Output