Delete Columns to Make Sorted: Column-Wise Validation

LeetCode Delete Columns to Make Sorted (problem 944) asks you to think about a grid of characters column by column instead of row by row. You are given an array of n strings strs, all of the same length. Imagine lining them up vertically so they form a grid. A column is "unsorted" if any character in that column is greater than the character directly below it. Your job is to count how many columns need to be deleted so that every remaining column is sorted from top to bottom.

Why this problem matters

This problem teaches you to iterate over a 2D structure by columns instead of rows. Most beginners default to row-major traversal because that is how arrays are laid out in memory. But many grid problems, including Sudoku validation, matrix transposition, and column-based queries, require you to think column-first. Delete Columns to Make Sorted is a gentle way to practice that mental shift.

It also reinforces the idea of early termination. Once you find a single pair of characters that violates sorted order in a column, you can stop checking that column and move to the next. This "break on first violation" pattern appears in validation problems everywhere.

The brute force approach

For this problem, the brute force approach and the optimal solution are essentially the same thing. You must check every column to determine if it is sorted, and there is no way to skip columns without inspecting them. The only question is how you iterate.

The direct approach: for each column index j, scan down the rows comparing strs[i][j] with strs[i + 1][j]. If you ever find a pair where the upper character is greater than the lower one, that column is unsorted. Count it and move on.

def minDeletionSize(strs):
    count = 0
    for j in range(len(strs[0])):
        for i in range(len(strs) - 1):
            if strs[i][j] > strs[i + 1][j]:
                count += 1
                break
    return count

There is no clever shortcut that avoids checking each column. The grid could have any arrangement of characters, so you need to inspect every column at least once. This makes the brute force approach also the optimal one.

The key insight: column-wise iteration

The trick is not about algorithmic cleverness. It is about getting the loop nesting right. Your outer loop iterates over columns (j), and your inner loop iterates over rows (i). This is the opposite of how you would normally read strings left to right.

Within each column, you compare adjacent rows. The moment you find strs[i][j] > strs[i + 1][j], you know this column is unsorted. You increment your counter and break out of the inner loop. No need to keep checking the rest of that column.

Walking through it step by step

Let's trace through strs = ["cba", "daf", "ghi"]. The grid has 3 rows and 3 columns. We check each column top to bottom, counting the unsorted ones.

The solution

def minDeletionSize(strs):
    count = 0
    for j in range(len(strs[0])):
        for i in range(len(strs) - 1):
            if strs[i][j] > strs[i + 1][j]:
                count += 1
                break
    return count

The outer loop walks each column index j from 0 to the string length. The inner loop walks each row index i from 0 to n - 2, comparing row i with row i + 1. If the comparison fails, we count that column and break immediately. After processing every column, count holds the answer.

Python's string comparison works character by character using Unicode values, so strs[i][j] > strs[i + 1][j] correctly checks alphabetical order. No special handling is needed for uppercase vs lowercase because the problem guarantees lowercase English letters.

Complexity analysis

In the worst case (every column is sorted), you visit every cell in the grid exactly once. In the best case (every column fails on the first pair), you visit only m cells. Either way, the time is bounded by O(n * m), which is optimal since you may need to read every character.

Building blocks

1. Column-wise iteration

The pattern of iterating a grid by columns instead of rows:

for j in range(num_cols):
    for i in range(num_rows):
        process(grid[i][j])

This same traversal order appears in problems like Valid Sudoku (checking each column for duplicates), Transpose Matrix (swapping row and column indices), and any problem that asks you to analyze vertical slices of a 2D structure. Once the column-first loop is second nature, these problems become mechanical.

2. Early termination on violation

The pattern of breaking out of a loop the moment a condition fails:

for i in range(len(sequence) - 1):
    if violates_constraint(sequence[i], sequence[i + 1]):
        handle_violation()
        break

This is the "is this sequence sorted?" check. You scan adjacent pairs and stop at the first violation. The same pattern appears in checking if an array is monotonic, validating sorted order in a BST's inorder traversal, and anywhere you need a yes/no answer about sequential ordering.

Edge cases

Before submitting, make sure your solution handles these:

• Single string ["abc"]: no adjacent rows to compare, so every column is trivially sorted. Return 0.
• Single character strings ["a", "b", "c"]: one column, and it is sorted. Return 0.
• All columns unsorted ["zyx", "wvu", "tsr"]: every column has characters in descending order. Return the total number of columns.
• All columns sorted ["abc", "bcd", "cde"]: every column is in ascending order. Return 0.
• Two strings ["ba", "ab"]: column 0 has b, a (unsorted). Column 1 has a, b (sorted). Return 1.
• Identical strings ["aaa", "aaa"]: every column has equal characters, which counts as sorted. Return 0.

Common mistakes

1. Iterating rows first instead of columns. If your outer loop is over rows and your inner loop is over columns, you are scanning horizontally, not vertically. The problem asks about column-wise sorted order, so the outer loop must be over column indices.

2. Forgetting to break after finding a violation. Without the break, you might count a single column multiple times if it has more than one out-of-order pair. Each column should contribute at most 1 to the count.

3. Off-by-one on the row range. The inner loop compares row i with row i + 1, so it should run from 0 to n - 2 (inclusive). Running to n - 1 would cause an index-out-of-bounds error when accessing strs[i + 1].

4. Using >= instead of >. Equal characters are fine. A column with ["a", "a", "b"] is sorted. Only strictly greater values (where a character comes after the next one alphabetically) indicate an unsorted column.

From understanding to recall

This problem is simple to understand, but the column-first iteration pattern is worth drilling until it is automatic. In an interview, you do not want to pause and think about whether i or j should be the outer loop. You want that decision to be instant.

Practice writing the nested loop from scratch: outer loop on columns, inner loop on rows, compare adjacent rows, break on violation. Once you can reproduce it without hesitation, the pattern transfers directly to harder grid problems where column-wise traversal is just one piece of a larger puzzle.

The column iteration and early-termination patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Valid Sudoku - Grid traversal checking row/column constraints
• Sort Colors - Array sorting with partitioning
• Rotate Image - Matrix manipulation patterns

CodeBricks breaks the Delete Columns to Make Sorted LeetCode problem into its column-wise iteration and early-termination building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid validation question shows up in your interview, you do not think about it. You just write it.