algoadvance

Leetcode 944. 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 ith column is the ith character of each string. You need to delete columns that are not sorted lexicographically, and return the number of columns that you will delete.

Example:

Input: strs = ["cba","daf","ghi"]
Output: 1
Explanation: We will delete column 1 (0-indexed), since it is not sorted: "b" > "a".

Clarifying Questions

1. What are the constraints on the lengths of the strings?
   • All strings in strs are of the same length.
2. What characters are the strings composed of?
   • The strings are composed of lowercase English letters.
3. Do we need to consider empty strings or strings of length 1?
   • The problem doesn’t specify these edge cases explicitly, but normally we’ll assume all strings are non-empty and at least of length 1.

Strategy

1. Iterate through each column of the strings.
2. Compare adjacent rows within the current column to verify if it is sorted in lexicographical order.
3. If any column is not sorted, count it as a column to be deleted.
4. Return the count of such columns.

Code

Let’s write the code in C++ to solve this problem:

#include <vector>
#include <string>

class Solution {
public:
    int minDeletionSize(std::vector<std::string>& strs) {
        // Calculate the number of strings and the length of each string
        int numStrings = strs.size();
        int strLength = strs[0].size();
        
        // Initialize a counter for columns to delete
        int columnsToDelete = 0;
        
        // Iterate through each column by character index
        for (int col = 0; col < strLength; ++col) {
            // Check the column for non-lexicographic order
            for (int row = 1; row < numStrings; ++row) {
                if (strs[row][col] < strs[row - 1][col]) {
                    columnsToDelete++;
                    break;  // No need to check further in this column, it's invalid already
                }
            }
        }
        
        return columnsToDelete;
    }
};

Time Complexity

• Time Complexity: O(n * m), where n is the number of strings and m is the length of each string.
  • We iterate through each column (up to m times).
  • For each column, we compare characters in n-1 pairs (hence, O(n) for each column).
• Space Complexity: O(1). We use a constant amount of additional space irrespective of the input size.

This approach ensures that we efficiently check each column to see if any deletions are necessary and keep track of the count of such columns.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?