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.length`
• `1 <= n <= 100`
• `1 <= strs[i].length <= 1000`
• `strs[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;
}
}
``````
Copy The Code &

Input

cmd
strs = ["a","b"]

#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;
};
``````
Copy The Code &

Input

cmd
strs = ["a","b"]

#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])))
``````
Copy The Code &

Input

cmd
strs = ["zyx","wvu","tsr"]

Output

cmd
3

#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;
}
}
}
``````
Copy The Code &

Input

cmd
strs = ["zyx","wvu","tsr"]

Output

cmd
3