We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delete Columns to Make Sorted

Number: 981

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

Given an array of n strings of the same length, form a grid where each string is a row. Determine the number of columns that are not in lexicographic order (top-to-bottom). For each column, if the characters are not sorted, then that column must be deleted.

Key Insights

  • The grid can be viewed column by column.
  • For each column, check if every character is less than or equal to the character in the same column of the next row.
  • Count columns that fail the sorted order condition.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of strings and m is the length of each string. Space Complexity: O(1) extra space (ignoring input storage).

Solution

We iterate over each column index from 0 to m-1. For every column, we compare each character with the one right below it across all rows. If any character is greater than the one beneath it, that column is considered unsorted and we increment our delete counter. The solution uses a simple iterative approach with nested loops, ensuring that all characters in each column satisfy the sorted order condition.

Code Solutions

# Python solution with detailed comments

def minDeletionSize(strs):
    # Number of columns is determined by the length of the first string
    if not strs:
        return 0
    num_cols = len(strs[0])
    num_rows = len(strs)
    delete_count = 0  # Counter for columns that are not sorted
    
    # Iterate over each column index
    for col in range(num_cols):
        # Check if the current column is sorted
        for row in range(1, num_rows):
            # if current character is less than previous character in the column, column unsorted
            if strs[row][col] < strs[row-1][col]:
                delete_count += 1  # Mark this column for deletion
                break  # Stop checking this column further
                
    return delete_count

# Example usage:
print(minDeletionSize(["cba", "daf", "ghi"]))  # Expect output: 1
← Back to All Questions