Taro Logo

Delete Columns to Make Sorted

#489 Most AskedEasy
15 views
Topics:
ArraysStrings

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", "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.

Example 1:

Input: strs = ["cba","daf","ghi"]
Output: 1
Explanation: The grid looks as follows:
  cba
  daf
  ghi
Columns 0 and 2 are sorted, but column 1 is not, so you only need to delete 1 column.

Example 2:

Input: strs = ["a","b"]
Output: 0
Explanation: The grid looks as follows:
  a
  b
Column 0 is the only column and is sorted, so you will not delete any columns.

Example 3:

Input: strs = ["zyx","wvu","tsr"]
Output: 3
Explanation: The grid looks as follows:
  zyx
  wvu
  tsr
All 3 columns are not sorted, so you will delete all 3.

Constraints:

  • n == strs.length
  • 1 <= n <= 100
  • 1 <= strs[i].length <= 1000
  • 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 the input array of strings, and what is the maximum length of each individual string?
  2. Can the input array be empty or contain null/empty strings?
  3. Is the sorting to be done lexicographically based on ASCII values, or is there a different comparison criterion?
  4. If a column has *some* characters out of order, but also *some* characters in order, should that column be deleted?
  5. Are all strings in the input array guaranteed to be of the same length?

Brute Force Solution

Approach

Imagine you have a list of words stacked on top of each other. The goal is to find the fewest number of columns to remove so that the words are sorted alphabetically when read from top to bottom. The brute force method tries out all possible combinations of columns to remove.

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

  1. First, consider removing no columns at all and check if the words are already sorted.
  2. Next, consider removing each column one at a time and see if removing that specific column makes the words sorted.
  3. Then, try removing every possible pair of columns to see if that helps sort the words. Keep going, testing every possible combination of two columns removed.
  4. Continue this process, trying to remove every possible group of three columns, four columns, and so on, until you have tried every combination of column removals.
  5. For each combination of columns that you remove, check if the remaining columns make the words sorted alphabetically from top to bottom.
  6. Keep track of how many columns you removed for each combination that results in sorted words.
  7. Finally, choose the combination that removed the fewest number of columns while still resulting in sorted words. That's your 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_columns_to_remove = string_length

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

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

        is_sorted = True

        # Construct strings with only the kept columns
        modified_strings = []
        for string in strings:
            modified_string = ''
            for column_index in columns_to_keep:
                modified_string += string[column_index]
            modified_strings.append(modified_string)

        # Check if the strings are sorted
        for string_index in range(number_of_strings - 1):
            if modified_strings[string_index] > modified_strings[string_index + 1]:
                is_sorted = False
                break

        if is_sorted:
            # Update the minimum number of columns to remove
            minimum_columns_to_remove = min(minimum_columns_to_remove, columns_to_remove_count)

    return minimum_columns_to_remove

Big(O) Analysis

Time Complexity
O(2^m * n) – The brute force approach iterates through all possible subsets of columns to remove, where m is the number of columns and n is the number of rows. Generating all subsets takes O(2^m) time. For each subset, we need to check if the remaining columns are sorted lexicographically, which takes O(n) time in the worst case, as we need to compare each row (word). Therefore, the overall time complexity is O(2^m * n), where 2^m represents the power set of column combinations and n represents the number of rows.
Space Complexity
O(2^M) – The described brute force method implicitly explores all possible subsets of columns to remove. Since there are M columns, where M is the number of columns in the input array, the algorithm effectively generates all 2^M possible combinations of columns to remove. While the plain english description avoids specifying explicitly how the combinations are managed, generating and/or storing these combinations, even temporarily during the recursion or iteration, implies an auxiliary space usage proportional to the number of combinations, up to 2^M. Furthermore, for each such combination, it checks whether removing those columns results in a sorted array of strings and that check might require further temporary storage with a maximum size limited by the number of input strings or size of strings. Therefore, the dominant factor is the generation of 2^M combinations, making the overall auxiliary space complexity O(2^M).

Optimal Solution

Approach

The key is to examine the input column by column. If a column disrupts the sorted order of the rows, we count it for deletion. We only need to focus on adjacent rows to determine if a column creates an out-of-order situation.

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

  1. Go through the columns one at a time, from left to right.
  2. For each column, compare the characters in each pair of adjacent rows.
  3. If at any point in a column, a character in one row is greater than the character in the row below it, then that column needs to be deleted.
  4. If a column needs to be deleted, increment our 'delete' counter.
  5. Move to the next column and repeat until all columns are checked.
  6. The final 'delete' counter represents the minimum number of columns to delete to make all rows sorted.

Code Implementation

def delete_columns_to_make_sorted(strings):
    number_of_columns_to_delete = 0
    number_of_columns = len(strings[0])

    for column_index in range(number_of_columns):
        # Check each column to determine if it needs to be deleted.
        for row_index in range(len(strings) - 1):
            # Compare current row with the next row
            if strings[row_index][column_index] > strings[row_index + 1][column_index]:
                # Found a column that needs to be deleted.
                number_of_columns_to_delete += 1

                break

    return number_of_columns_to_delete

Big(O) Analysis

Time Complexity
O(m*n) – The algorithm iterates through each of the 'm' columns. For each column, it compares characters in 'n' adjacent rows. Therefore, the time complexity is determined by the product of the number of columns and the number of rows. The comparison operations within the loops contribute constant time, and the loops are the dominating factor. The overall time complexity can be represented as O(m*n), where 'm' is the width (number of columns) and 'n' is the height (number of rows) of the input array of strings.
Space Complexity
O(1) – The algorithm iterates through the input `strs` and compares characters within the given strings. It uses a single integer variable, `delete_count`, to keep track of the columns to be deleted. Since only a constant amount of extra memory is used, irrespective of the number of rows or columns in the input, the space complexity is O(1).

Edge Cases

Null or empty input array
How to Handle:
Return 0 as there are no columns to potentially delete.
Array containing an empty string
How to Handle:
Treat the empty string as the smallest possible string and compare appropriately.
Array with only one string
How to Handle:
Return 0 as a single string is always sorted.
Strings of significantly varying lengths
How to Handle:
Iterate only up to the length of the shortest string, safely ignoring the longer strings' extra characters.
Strings with all the same characters
How to Handle:
The solution should correctly identify these columns as sorted and not delete them.
Input array with a very large number of strings
How to Handle:
Ensure the solution uses a reasonably space-efficient algorithm, avoiding unnecessary memory allocations.
Strings containing non-ASCII characters
How to Handle:
Verify that the character comparison is based on Unicode code points and not ASCII values, to handle characters from different languages.
Very long strings in the input array
How to Handle:
Avoid unnecessary string copying to optimize for performance if using an implementation that might lead to out-of-memory issues when copying very long strings frequently.
0/1718 completed