Delete Columns To Make Sorted - Leetcode Solution

Problem Statement:

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", "def", "ghi"] can be arranged as:

abc def ghi We want to delete columns that are not sorted ascendingly. More formally, we want to keep the columns such that for every pair of consecutive rows their characters are in ascending order.

Return the number of columns we need to delete.

Example: Input: strs = ["cba","daf","ghi"] Output: 1 Explanation: The grid looks as follows: cba daf ghi Columns 1 and 2 are not sorted in ascending order, so they have to be deleted.

Solution:

To solve the given problem leetcode has provided us with the following constraints,

All strings are of the same length, in other words, all rows have the same number of columns/questions.

The number of rows/answers to the questions is equal to the number of columns in the grid.

We need to keep columns that are sorted in ascending order for every pair of consecutive rows.

We cannot sort the strings as they all describe different questions.

As we have already mentioned, all strings are of the same length, so we will loop through the strings keeping track of each index, and then compare each character in the ith index of every string. Removing a column when such a mismatch has been found in that column.

We’ll start by initializing a variable ‘result’ to 0, which will; keep track of the number of columns that need to be deleted.

Then, we will loop through the length of the first string (or any of the strings), and compare each corresponding character in all the given strings, proceeding from the left to the right.

When a mismatch is found at any position, we increment the result variable and break from the inner loop, as there is a single mismatch in the pair of consecutive rows.

Finally, we return the value of the result variable.

Code:

Let’s take a look at the code implementing the above algorithm:

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

Complexity Analysis:

The above code loops through all characters of the string while comparing each character in every string.

Let’s say we have a total of s number of strings, and each string has a length l. Therefore, the time complexity of the code will be O(s*l), which is the product of the number of strings and string length.

In conclusion, the above code is an optimal solution to the given problem, given the constraints.

1