Delete Columns To Make Sorted Ii - Leetcode Solution

Problem Description:

Given a matrix M, return the number of columns that are not sorted (in ascending order).

We are allowed to delete columns that are not sorted. For example, given

M = ["cba", "daf", "ghi"]

the solution is 1 because we can delete the column "f" and the remaining columns are sorted ("ce" and "hi").

Solution:

First, initialize a variable count to 0 to keep track of the number of unsorted columns.

Then, iterate through each column in the matrix, and for each column, iterate through the characters in that column.

If a character in a column is less than the character in the previous column, then that column is not sorted. We increment the count of unsorted columns, break out of the inner loop, and move on to the next column.

We repeat this process for all columns in the matrix.

The final count will be the number of columns that are not sorted.

Algorithm:

1. Initialize a variable count to 0.
2. Check whether each column in the matrix is sorted or not by iterating through each column and each character in that column.
3. If a character in a column is less than the character in the previous column, increment the count of unsorted columns and break out of the loop.
4. Repeat this process for all columns in the matrix.
5. Return the count of unsorted columns.

Python Implementation:

def minDeletionSize(strs: List[str]) -> int: count = 0 for i in range(len(strs[0])): for j in range(1, len(strs)): if strs[j][i] < strs[j-1][i]: count += 1 break return count

Time Complexity: O(n*m), where n is the length of the list and m is the length of each string in the list.

Space Complexity: O(1) as we are not using any extra space.

Example Input and Output:

Input: ["cba", "daf", "ghi"] Output: 1

Input: ["a", "b"] Output: 0

Input: ["zyx", "wvu", "tsr"] Output: 3

Explanation:

In the first example, we can delete the column "f" to make the matrix sorted. In the second example, the matrix is already sorted, so the output is 0. In the third example, we need to delete all three columns to make the matrix sorted.

1