# Delete Columns to Make Sorted
**Difficulty:** EASY
[External](https://leetcode.com/problems/delete-columns-to-make-sorted)
Canonical: https://scaleengineer.com/dsa/problems/delete-columns-to-make-sorted
**Data structures:** Array, String
**Companies:** [Garmin](https://scaleengineer.com/companies/garmin)
---
## Problem
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.

# Approaches
## Column-by-Column Sorting and Comparison
This approach involves iterating through each column of the grid. For each column, we extract all its characters into a separate array. Then, we create a sorted version of this character array. By comparing the original character array with its sorted version, we can determine if the column was already sorted. If not, we increment a counter for the columns to be deleted.
**Time:** O(m * n log n), where `n` is the number of strings and `m` is the length of each string. For each of the `m` columns, we create an array of size `n` and sort it, which takes O(n log n) time. · **Space:** O(n). For each column, we create a temporary character array of size `n` to hold the column's characters.
**Pros:** Conceptually simple and easy to understand.; Clearly separates the logic for checking each column.
**Cons:** Less efficient in terms of both time and space compared to the optimal approach.; The sorting step for each column is computationally more expensive than a simple linear scan.
### Explanation
This method checks each column for sorted order by explicitly creating and sorting a representation of that column.

- Get the number of rows `n = strs.length` and columns `m = strs[0].length`.
- Initialize a counter `deleteCount = 0`.
- Loop through each column index `j` from 0 to `m-1`.
- For each column `j`, create a temporary character array `columnChars` of size `n`.
- Populate `columnChars` by iterating from `i = 0` to `n-1` and setting `columnChars[i] = strs[i].charAt(j)`.
- Create a copy of `columnChars`, let's call it `sortedColumnChars`.
- Sort `sortedColumnChars` lexicographically.
- Compare `columnChars` and `sortedColumnChars`. If they are not identical, it means the original column was not sorted.
- If the column was not sorted, increment `deleteCount`.
- After checking all columns, return `deleteCount`.

```java
import java.util.Arrays;

class Solution {
    public int minDeletionSize(String[] strs) {
        if (strs == null || strs.length == 0) {
            return 0;
        }
        int numRows = strs.length;
        int numCols = strs[0].length();
        int deleteCount = 0;

        for (int j = 0; j < numCols; j++) {
            char[] columnChars = new char[numRows];
            for (int i = 0; i < numRows; i++) {
                columnChars[i] = strs[i].charAt(j);
            }

            char[] sortedColumnChars = Arrays.copyOf(columnChars, numRows);
            Arrays.sort(sortedColumnChars);

            if (!Arrays.equals(columnChars, sortedColumnChars)) {
                deleteCount++;
            }
        }
        return deleteCount;
    }
}
```
### Algorithm
- Get the number of rows `n = strs.length` and columns `m = strs[0].length`.
- Initialize a counter `deleteCount = 0`.
- Loop through each column index `j` from 0 to `m-1`.
- For each column `j`, create a temporary character array `columnChars` of size `n`.
- Populate `columnChars` by iterating from `i = 0` to `n-1` and setting `columnChars[i] = strs[i].charAt(j)`.
- Create a copy of `columnChars`, let's call it `sortedColumnChars`.
- Sort `sortedColumnChars` lexicographically.
- Compare `columnChars` and `sortedColumnChars`. If they are not identical, it means the original column was not sorted.
- If the column was not sorted, increment `deleteCount`.
- After checking all columns, return `deleteCount`.

## Direct Column Traversal
This is the most efficient approach. Instead of creating temporary arrays and sorting them, we can directly check if each column is sorted by iterating through it. We traverse the grid column by column. For each column, we compare each character with the one in the row just above it. If we find any pair of characters that violates the sorted order (i.e., `char_current < char_above`), we know this column is not sorted. We can then increment our deletion counter and immediately move on to the next column, as there's no need to check the rest of the current one.
**Time:** O(m * n), where `n` is the number of strings and `m` is the length of each string. In the worst case, we visit every character in the grid once. · **Space:** O(1). We only use a few variables to keep track of indices and the count, requiring constant extra space.
**Pros:** Optimal time and space complexity.; Avoids unnecessary work by breaking early from checking a column as soon as an unsorted pair is found.
**Cons:** There are no significant cons to this approach as it is the most efficient solution.
### Explanation
This optimal method iterates through the grid and checks each column's sorted property in-place, without creating extra data structures for each column.

- Get the number of rows `n = strs.length` and columns `m = strs[0].length`.
- Initialize a counter `deleteCount = 0`.
- Loop through each column index `j` from 0 to `m-1`.
- For each column `j`, loop through the row index `i` from 1 to `n-1`.
- Compare the character at `strs[i].charAt(j)` with the character at `strs[i-1].charAt(j)`.
- If `strs[i].charAt(j) < strs[i-1].charAt(j)`, the column is not sorted.
- In this case, increment `deleteCount` and `break` from the inner loop (over rows) to proceed to the next column.
- After iterating through all columns, return `deleteCount`.

```java
class Solution {
    public int minDeletionSize(String[] strs) {
        if (strs == null || strs.length == 0) {
            return 0;
        }
        int numRows = strs.length;
        int numCols = strs[0].length();
        int deleteCount = 0;

        // Iterate over each column
        for (int j = 0; j < numCols; j++) {
            // Iterate over each row in the current column
            for (int i = 1; i < numRows; i++) {
                // Compare the character with the one in the previous row
                if (strs[i].charAt(j) < strs[i-1].charAt(j)) {
                    // Column is not sorted, increment count and move to the next column
                    deleteCount++;
                    break;
                }
            }
        }
        return deleteCount;
    }
}
```
### Algorithm
- Get the number of rows `n = strs.length` and columns `m = strs[0].length`.
- Initialize a counter `deleteCount = 0`.
- Loop through each column index `j` from 0 to `m-1`.
- For each column `j`, loop through the row index `i` from 1 to `n-1`.
- Compare the character at `strs[i].charAt(j)` with the character at `strs[i-1].charAt(j)`.
- If `strs[i].charAt(j) < strs[i-1].charAt(j)`, the column is not sorted.
- In this case, increment `deleteCount` and `break` from the inner loop (over rows) to proceed to the next column.
- After iterating through all columns, return `deleteCount`.

# Solutions
### Java

```java
class Solution {
public
  int minDeletionSize(String[] strs) {
    int m = strs[0].length(), n = strs.length;
    int ans = 0;
    for (int j = 0; j < m; ++j) {
      for (int i = 1; i < n; ++i) {
        if (strs[i].charAt(j) < strs[i - 1].charAt(j)) {
          ++ans;
          break;
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minDeletionSize(vector<string> &strs) {
    int n = strs.size();
    int m = strs[0].size();
    int res = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n - 1; ++j) {
        if (strs[j][i] > strs[j + 1][i]) {
          res++;
          break;
        }
      }
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    def minDeletionSize(self, strs: List[str]) -> int: m, n = len(strs[0]), len(strs) ans = 0 for j in range(m): for i in range(1, n): if strs[i][j] < strs[i - 1][j]: ans += 1 break return ans

```