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.

From: LeetCode
Link: 944. Delete Columns to Make Sorted

Solution:

Ideas:

• int cols = strlen(strs[0]);: Get the number of columns in the grid, which is the length of any string in the list (since all strings are the same length).

• Outer loop (for (int col = 0; col < cols; col++)): This iterates through each column.

• Inner loop (for (int row = 1; row < strsSize; row++)): This checks if the current column is sorted. If the current character (strs[row][col]) is less than the previous character (strs[row - 1][col]), the column is unsorted, and we increment the deletedColumns counter.

• return deletedColumns;: Return the number of unsorted columns.

Code:

int minDeletionSize(char** strs, int strsSize) {
    int cols = strlen(strs[0]); // All strings are of the same length.
    int deletedColumns = 0;

    // Loop through each column
    for (int col = 0; col < cols; col++) {
        // Check if the column is sorted
        for (int row = 1; row < strsSize; row++) {
            if (strs[row][col] < strs[row - 1][col]) {
                deletedColumns++;
                break; // No need to check further, this column is to be deleted.
            }
        }
    }
    
    return deletedColumns;
}