Solution For Delete Columns To Make Sorted

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.

Step by Step Implementation For Delete Columns To Make Sorted

class Solution { 
    public int minDeletionSize(String[] A) { 
        int count = 0; 
        for(int i = 0; i < A[0].length(); i++) { 
            for(int j = 0; j < A.length - 1; j++) { 
                if(A[j].charAt(i) > A[j+1].charAt(i)) { 
                    count++; 
                    break; 
                } 
            } 
        } 
        return count; 
    } 
}

def minDeletionSize(self, A: List[str]) -> int:
        ans = 0
        for col in zip(*A):
            if any(col[i] > col[i+1] for i in range(len(col) - 1)):
                ans += 1
        return ans

/**
 * @param {string[]} A
 * @return {number}
 */
var minDeletionSize = function(A) {
    let count = 0;
    
    for (let i = 0; i < A[0].length; i++) {
        for (let j = 0; j < A.length - 1; j++) {
            if (A[j].charCodeAt(i) > A[j + 1].charCodeAt(i)) {
                count++;
                break;
            }
        }
    }
    
    return count;
};

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

public class Solution {
    public int MinDeletionSize(string[] A) {
        // Initialize a counter for the number of deletions needed
        int deletions = 0;
        
        // Loop through each column in the array
        for (int col = 0; col < A[0].Length; col++) {
            // Loop through each row in the array
            for (int row = 0; row < A.Length - 1; row++) {
                // If the current character in the column is greater
                // than the next character in the column, we need
                // to delete that column
                if (A[row][col] > A[row + 1][col]) {
                    deletions++;
                    break;
                }
            }
        }
        
        return deletions;
    }
}