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

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

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

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):
    if not grid:
        return 0

    if len(grid) == 1:
        return 0

    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

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

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"]


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

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.