algoadvance

Leetcode 944. Delete Columns to Make Sorted

Problem Statement

You are given an array of n strings strs, each of the same length.

The strings can be arranged such that there is one string per row, 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.

Clarifying Questions

  1. Are all input strings guaranteed to have the same length?
    • Yes, as per the problem statement.
  2. Can the input strings contain any characters other than lowercase alphabets?
    • The problem implicitly assumes that strings contain only lowercase English letters.
  3. What is the range of n (number of strings) and the length of each string?
    • Per typical constraints: 1 <= n <= 1000, 1 <= length of strings <= 1000.

Strategy

  1. Loop over each column (from 0 to length-1 of the strings).
  2. For each column, check each adjacent pair of strings to see if the characters in the current column are in non-decreasing order.
  3. If a column is found that is not sorted, increment the count of columns to delete.
  4. Return the count of columns to delete.

Code

class Solution {
    public int minDeletionSize(String[] strs) {
        int numCols = strs[0].length();
        int numRows = strs.length;
        int columnsToDelete = 0;
        
        for (int col = 0; col < numCols; col++) {
            for (int row = 1; row < numRows; row++) {
                if (strs[row].charAt(col) < strs[row-1].charAt(col)) {
                    columnsToDelete++;
                    break;
                }
            }
        }
        
        return columnsToDelete;
    }
}

Time Complexity

This ensures that we can handle the worst-case scenario efficiently, whether sorting or checking constraints on the input strings.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI