Domain 1EasyCORE

Delete Columns to Make Sorted

The problem requires us to determine the number of columns in a grid formed by an array of strings that are not sorted lexicographically. Each string in the array has the same length. We need to delete these unsorted columns and return the count of such deletions.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Greedy

944. Delete Columns to Make Sorted

Model: qwen2.5-coder:14b
Topics: Greedy
FAANG asked: 1
Acceptance rate: 70.9%


Problem Breakdown

The problem requires us to determine the number of columns in a grid formed by an array of strings that are not sorted lexicographically. Each string in the array has the same length. We need to delete these unsorted columns and return the count of such deletions.

Inputs:

  • An array of n strings, where each string has the same length.
  • The number of strings n ranges from 1 to 100.
  • Each string’s length can range from 1 to 1000.
  • Strings consist only of lowercase English letters.

Outputs:

  • An integer representing the number of columns that need to be deleted.

Implicit Constraints or Tricky Edge Cases:

  • If there is only one string, all columns are trivially sorted.
  • If all strings are identical, no columns will need to be deleted.
  • The grid can be very large (up to 100,000 characters per column), so the solution should be efficient in terms of both time and space.

Intuition

A brute-force approach would involve checking each column individually to see if it is sorted. This would have a time complexity of O(n * m^2), where n is the number of strings and m is the length of each string, which could be inefficient given the constraints.

The key insight is to recognize that we can check each column in linear time by iterating through the characters of each string in the column. If any character is less than the previous one, the column is not sorted, and we should count it for deletion.

Approach

  1. Initialize a counter delete_count to zero.
  2. Iterate over each column index from 0 to m-1.
  3. For each column, iterate through each string in the array starting from the second string.
  4. Compare the current character with the previous one in the same column.
  5. If any character is less than the previous one, increment the delete_count and break out of the inner loop to move to the next column.
  6. Return the delete_count.

Complexity Analysis

  • Time Complexity: O(n * m), where n is the number of strings and m is the length of each string. We iterate through each character in the grid once.
  • Space Complexity: O(1). We only use a constant amount of extra space for the counter.

Solution

def minDeletionSize(strs):
    delete_count = 0
    m = len(strs[0])  # Number of columns
    
    for col in range(m):
        for row in range(1, len(strs)):
            if strs[row][col] < strs[row - 1][col]:
                delete_count += 1
                break
    
    return delete_count

Edge Cases Handled

  • Single String: If there is only one string, the loop will not execute, and delete_count remains zero.
  • All Identical Strings: All columns will be sorted, so delete_count remains zero.
  • Large Grids: The solution efficiently handles large grids by iterating through each character in the grid once.