Taro Logo

Delete Columns to Make Sorted II

#566 Most AskedMedium
14 views
Topics:
ArraysStringsGreedy Algorithms

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

We may choose any deletion indices, and we delete all the characters in those indices for each string.

For example, if we have strs = ["abcdef","uvwxyz"] and deletion indices {0, 2, 3}, then the final array after deletions is ["bef", "vyz"].

Suppose we chose a set of deletion indices answer such that after deletions, the final array has its elements in lexicographic order (i.e., strs[0] <= strs[1] <= strs[2] <= ... <= strs[n - 1]). Return the minimum possible value of answer.length.

Example 1:

Input: strs = ["ca","bb","ac"]
Output: 1
Explanation: 
After deleting the first column, strs = ["a", "b", "c"].
Now strs is in lexicographic order (ie. strs[0] <= strs[1] <= strs[2]).
We require at least 1 deletion since initially strs was not in lexicographic order, so the answer is 1.

Example 2:

Input: strs = ["xc","yb","za"]
Output: 0
Explanation: 
strs is already in lexicographic order, so we do not need to delete anything.
Note that the rows of strs are not necessarily in lexicographic order:
i.e., it is NOT necessarily true that (strs[0][0] <= strs[0][1] <= ...)

Example 3:

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: We have to delete every column.

Constraints:

  • n == strs.length
  • 1 <= n <= 100
  • 1 <= strs[i].length <= 100
  • strs[i] consists of lowercase English letters.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What is the maximum length of each string in the input array, and what is the maximum number of strings in the array?
  2. Are the strings guaranteed to be of the same length? If not, how should columns beyond the length of the shortest string be handled?
  3. What does 'sorted' mean in this context? Is it lexicographically increasing in ASCII order?
  4. If deleting all columns results in the rows being sorted, is that a valid solution? In other words, can I delete *all* columns?
  5. If multiple sets of columns can be deleted to make the array sorted, should I return the minimum number of columns deleted, or is any valid solution acceptable?

Brute Force Solution

Approach

The brute force method for this problem is all about trying every possible combination of column deletions to find one that works. We systematically check each possibility, even if it takes a very long time. We'll explore every combination of columns we can delete and see if the remaining ones make the rows sorted.

Here's how the algorithm would work step-by-step:

  1. First, consider the possibility of deleting no columns at all and check if the rows are sorted in lexicographical order (like words in a dictionary).
  2. Next, consider deleting only the first column, then only the second column, and so on, checking the sorted property after each deletion.
  3. Now, consider deleting two columns at a time. Try deleting the first and second columns, then the first and third columns, and so on, again checking if the remaining rows are sorted.
  4. Continue this process for deleting three columns at a time, then four, and so on, up to deleting all but one column.
  5. For each combination of column deletions, carefully examine the resulting rows to ensure they are sorted in lexicographical order from top to bottom. If a combination makes the rows sorted, record the number of columns that were deleted.
  6. After checking all possible combinations of deleted columns, identify the combination that resulted in the fewest number of deleted columns while still ensuring that the remaining rows are lexicographically sorted.
  7. The number of deleted columns in that best combination is our answer.

Code Implementation

def delete_columns_to_make_sorted_brute_force(strings):
    number_of_strings = len(strings)
    if number_of_strings <= 1:
        return 0

    string_length = len(strings[0])
    minimum_deleted_columns = string_length

    for i in range(1 << string_length):
        deleted_columns_count = 0
        columns_to_keep = []

        for column_index in range(string_length):
            if (i >> column_index) & 1:
                deleted_columns_count += 1
            else:
                columns_to_keep.append(column_index)

        is_sorted = True

        # Iterate to see if the string is sorted after deleting columns.
        for string_index in range(1, number_of_strings):
            previous_string = ""
            current_string = ""

            for column_index in columns_to_keep:
                previous_string += strings[string_index - 1][column_index]
                current_string += strings[string_index][column_index]

            if previous_string > current_string:
                is_sorted = False
                break

        # If the column removal yields a sorted result.
        if is_sorted:
            minimum_deleted_columns = min(minimum_deleted_columns, deleted_columns_count)

    return minimum_deleted_columns

Big(O) Analysis

Time Complexity
O(2^m * n * m) – The brute force approach explores all possible subsets of columns to delete. If there are m columns, there are 2^m possible subsets. For each subset, we need to verify if the remaining columns result in sorted rows. This check involves iterating through the n rows and comparing m (or fewer) column values in the worst case. Thus, the time complexity is O(2^m * n * m) where n is the number of rows and m is the number of columns. The term 2^m dominates the complexity as m, the number of columns, increases.
Space Complexity
O(2^M) – The brute force method iterates through all possible combinations of column deletions. In the worst-case scenario, it might need to store the combinations of columns to be deleted or kept which can be represented by a binary string of length M (where M is the number of columns), resulting in 2^M possible combinations. While checking each combination, the space used to store or copy the modified strings (rows after deletion) is also considered, although the dominant factor remains the storage of combinations. Therefore, the auxiliary space complexity is approximately O(2^M), reflecting the exponential growth in possible combinations with increasing column count.

Optimal Solution

Approach

The core idea is to efficiently identify and eliminate columns that would disrupt the sorted order of rows. We achieve this by iteratively checking rows and intelligently tracking which rows are already sorted, avoiding unnecessary comparisons and deletions.

Here's how the algorithm would work step-by-step:

  1. Start by assuming no columns need to be deleted.
  2. Go through the columns one by one, from left to right.
  3. For each column, compare the letters in that column for rows that aren't yet known to be sorted.
  4. If a column introduces a situation where letters are out of order in previously unsorted rows, mark that column for deletion.
  5. If a column doesn't introduce any out-of-order issues, update the record of which rows are now confirmed to be sorted based on that column.
  6. After checking all columns, simply count how many columns were marked for deletion to get the final answer.

Code Implementation

def min_deletion_size(strs): 
    number_of_rows = len(strs)
    number_of_columns = len(strs[0])
    deleted_column_count = 0

    sorted_rows = [False] * number_of_rows

    for column_index in range(number_of_columns):
        currently_sorted = sorted_rows[:]
        for row_index in range(1, number_of_rows):
            # Only check unsorted rows.
            if not sorted_rows[row_index]:
                if strs[row_index][column_index] < strs[row_index - 1][column_index]:

                    deleted_column_count += 1
                    break

                # Rows are sorted if current char is equal
                elif strs[row_index][column_index] > strs[row_index - 1][column_index]:
                    currently_sorted[row_index] = True
        else:
            # This column didn't need to be deleted, update sorted rows.
            # Need to update sorted rows only if no column deletion occurred
            sorted_rows = currently_sorted

    return deleted_column_count

Big(O) Analysis

Time Complexity
O(n*m) – The algorithm iterates through each of the m columns. For each column, it iterates through the n rows to check if the column maintains the sorted order of the rows. The process of checking each column requires iterating through potentially all rows in the worst case. Therefore, the time complexity is O(n*m), where n is the number of rows and m is the number of columns.
Space Complexity
O(N) – The algorithm uses an auxiliary boolean array, sorted, to keep track of which rows are sorted. The size of this array is equal to the number of rows in the input, which we can denote as N. This sorted array is the dominant factor in the space complexity, as it scales linearly with the number of rows. Therefore, the space complexity is O(N).

Edge Cases

Empty input array
How to Handle:
Return 0, as no columns need to be deleted in an empty array.
Array with only one string
How to Handle:
Return 0, as a single string is always considered sorted.
Strings with different lengths
How to Handle:
The algorithm must handle strings of unequal length by stopping comparison at the shortest string's length and continuing processing.
Array with strings of maximum allowed length (or close to it)
How to Handle:
Ensure algorithm efficiency prevents excessive memory usage or runtime, especially when many strings are close to maximum length.
All strings are identical
How to Handle:
Return 0, as no columns need to be deleted if all strings are the same.
All strings are sorted lexicographically
How to Handle:
Return 0, as no columns need to be deleted because the array is already sorted.
Strings with non-ASCII characters (Unicode)
How to Handle:
Ensure the character comparison logic correctly handles Unicode characters based on their lexicographical order.
Very large input array size
How to Handle:
The algorithm should be optimized for space and time to handle arrays containing a large number of strings efficiently, potentially needing to avoid quadratic complexities.
0/1916 completed