How to Count Unsorted Columns in a Python Grid

Counting unsorted columns in a 2D grid is a common algorithmic challenge that appears in coding interviews and competitive programming. Given a grid of characters or numbers, the goal is to determine how many columns are not sorted in ascending order from top to bottom.

In this guide, you will learn multiple approaches to solve this problem, from concise Pythonic one-liners to optimized solutions for large grids. Each method is explained with examples and output so you can understand the trade-offs and choose the right one for your situation.

Understanding the Problem

Consider a grid represented as a list of strings, where each string is a row and each character at a given index forms a column:

Row 0:  c  b  a
Row 1:  d  a  f
Row 2:  g  h  i

• Column 0 (c, d, g): sorted in ascending order.
• Column 1 (b, a, h): not sorted, because a comes after b.
• Column 2 (a, f, i): sorted in ascending order.

The answer is 1 unsorted column.

Using zip() for Column Transposition

The most Pythonic approach uses zip(*grid) to transpose the grid, converting columns into tuples that you can process as sequences:

grid = ["cba", "daf", "ghi"]

unsorted_count = 0
for col in zip(*grid):
    if list(col) != sorted(col):
        unsorted_count += 1

print(unsorted_count)

Output:

1

The zip(*grid) call unpacks the grid rows and zips them together, producing tuples for each column: ('c', 'd', 'g'), ('b', 'a', 'h'), and ('a', 'f', 'i'). Comparing each column to its sorted version reveals whether it is in ascending order.

One-Liner with a Generator Expression

You can condense the same logic into a single expression:

grid = ["cba", "daf", "ghi"]

unsorted_count = sum(1 for col in zip(*grid) if list(col) != sorted(col))

print(unsorted_count)

Output:

1

This is concise and readable for anyone familiar with Python generator expressions, though the explicit loop version may be clearer when the logic needs to be extended.

Optimized Approach with Early Exit

The sorted() comparison has O(n log n) complexity per column, where n is the number of rows. For large grids, a manual pairwise check runs in O(n) per column and can exit early as soon as it finds a single out-of-order pair:

def count_unsorted_columns(grid):
    if not grid or not grid[0]:
        return 0

    rows = len(grid)
    cols = len(grid[0])
    count = 0

    for c in range(cols):
        for r in range(rows - 1):
            if grid[r][c] > grid[r + 1][c]:
                count += 1
                break  # Column is unsorted, no need to check further

    return count

grid = ["cba", "daf", "ghi"]
print(count_unsorted_columns(grid))

Output:

1

tip

The early break provides significant performance gains when unsorted elements appear near the top of a column. In the best case, the function detects an unsorted column after checking just the first pair of rows.

Working with Numeric Grids

The same logic applies to grids containing numbers. Instead of strings, each row is a list of integers or floats:

grid = [
    [1, 3, 2],
    [2, 1, 4],
    [3, 5, 6]
]

unsorted_count = sum(1 for col in zip(*grid) if list(col) != sorted(col))

print(unsorted_count)

Output:

1

note

Observe that above:

• The middle column (3, 1, 5) is unsorted because 1 comes after 3.
• The other two columns are in ascending order.

Identifying Which Columns Are Unsorted

Instead of just counting, you can return the indices of the unsorted columns for further analysis or debugging:

def find_unsorted_columns(grid):
    unsorted_indices = []

    for idx, col in enumerate(zip(*grid)):
        if list(col) != sorted(col):
            unsorted_indices.append(idx)

    return unsorted_indices

grid = ["cba", "daf", "ghi"]
result = find_unsorted_columns(grid)

print(f"Unsorted column indices: {result}")
print(f"Total unsorted: {len(result)}")

Output:

Unsorted column indices: [1]
Total unsorted: 1

note

This is useful when you need to report or process the specific columns that fail the sorting check.

Counting Sorted Columns Instead

If your problem requires counting columns that are sorted, you can either check directly or subtract the unsorted count from the total:

grid = ["abc", "bcd", "cde"]

sorted_count = sum(1 for col in zip(*grid) if list(col) == sorted(col))
total_cols = len(grid[0])
unsorted_count = total_cols - sorted_count

print(f"Sorted: {sorted_count}, Unsorted: {unsorted_count}")

Output:

Sorted: 3, Unsorted: 0

Handling Edge Cases

A robust solution should account for empty grids, single-row grids, and rows of inconsistent lengths:

def count_unsorted_safe(grid):
    # Empty grid
    if not grid:
        return 0

    # Single row: all columns are trivially sorted
    if len(grid) == 1:
        return 0

    # Handle rows of different lengths by using the minimum
    min_cols = min(len(row) for row in grid)

    count = 0
    for c in range(min_cols):
        for r in range(len(grid) - 1):
            if grid[r][c] > grid[r + 1][c]:
                count += 1
                break

    return count

# Edge case tests
print(count_unsorted_safe([]))            # 0 (empty grid)
print(count_unsorted_safe(["abc"]))       # 0 (single row)
print(count_unsorted_safe(["ab", "bac"])) # uses only first 2 columns

Output:

0
0
0

warning

Ensure all rows have the same length before processing. Inconsistent row lengths can cause IndexError exceptions or produce incorrect results. The safe version above handles this by using the minimum row length, but in most problem statements the grid is guaranteed to be rectangular.

A Common Mistake: Forgetting That Single Rows Are Always Sorted

A subtle bug occurs when the function does not handle the single-row case:

grid = ["zyx"]

# Without the single-row check, zip(*grid) produces
# ('z',), ('y',), ('x',) which are all trivially sorted.
# In this specific case it works, but relying on it without
# an explicit check can mask logic errors in more complex variants.

unsorted = sum(1 for col in zip(*grid) if list(col) != sorted(col))
print(unsorted)

Output:

0

While zip(*grid) happens to handle this correctly for the basic problem, explicitly checking for single-row grids makes your intent clear and prevents issues in extended versions of the algorithm.

Method Comparison

Method	Readability	Time Complexity	Best For
zip() + sorted()	High	O(cols * rows log rows)	Small to medium grids
Generator expression	High	O(cols * rows log rows)	Concise solutions
Nested loop with break	Medium	O(cols * rows)	Large grids, performance-critical code
Index-returning variant	Medium	O(cols * rows log rows)	Debugging and detailed analysis

Conclusion

The zip(*grid) approach is the most Pythonic way to work with columns in a 2D grid.

• It transforms column-based problems into row-based operations that align naturally with Python's iteration patterns.
• For small to medium grids, comparing each transposed column to its sorted() version is clean and readable.
• For large grids where performance matters, the nested loop with early break avoids the overhead of sorting and can skip unnecessary comparisons as soon as a column is determined to be unsorted.
• Always handle edge cases like empty grids, single rows, and inconsistent row lengths to make your solution robust.