Minimum Swaps to Arrange a Binary Grid: Greedy Row Swap Pattern

You are given an n x n binary grid. In one step, you can choose two adjacent rows and swap them. Return the minimum number of swaps needed so that all the cells above the main diagonal are zeros. If it is impossible, return -1.

This is LeetCode 1536: Minimum Swaps to Arrange a Binary Grid, and it is a clean example of how a matrix problem reduces to a greedy selection problem once you find the right lens to look through.

Why this problem matters

Matrix problems often look intimidating because you think you need to manipulate individual cells. This problem teaches you to think at the row level instead. Once you realize the constraint is about trailing zeros per row, the entire 2D grid collapses into a 1D array of integers, and the problem becomes a greedy row placement task.

The greedy "find the nearest valid candidate and bubble it into place" technique appears in many other problems. It is the same pattern you use in selection sort, in problems that ask for minimum adjacent swaps, and in scheduling problems where you greedily pick the next best fit.

The key insight

For the grid to have all zeros above the main diagonal, row i must have at least n - 1 - i trailing zeros. Row 0 needs n - 1 trailing zeros. Row 1 needs n - 2. The last row needs 0.

Once you compute the trailing zeros for each row, you process the rows from top to bottom. For each position i, find the nearest row at position j >= i that has enough trailing zeros. Then bubble that row up from position j to position i using j - i adjacent swaps. If no valid row exists, the answer is -1.

This greedy choice is optimal because placing a row with more trailing zeros than needed at an earlier position wastes capacity. The nearest valid row minimizes the number of swaps for the current position without blocking future positions.

The solution

def min_swaps(grid: list[list[int]]) -> int:
    n = len(grid)
    trailing = []
    for row in grid:
        count = 0
        for j in range(n - 1, -1, -1):
            if row[j] == 0:
                count += 1
            else:
                break
        trailing.append(count)

    swaps = 0
    for i in range(n):
        need = n - 1 - i
        j = i
        while j < n and trailing[j] < need:
            j += 1
        if j == n:
            return -1
        while j > i:
            trailing[j], trailing[j - 1] = trailing[j - 1], trailing[j]
            j -= 1
            swaps += 1

    return swaps

Let's break down each piece.

The first loop computes the number of trailing zeros in each row. It scans from right to left, counting consecutive zeros until it hits a 1 or runs out of columns. This reduces the 2D grid to a 1D array trailing where trailing[r] is the number of trailing zeros in row r.

The main loop processes positions from top to bottom. For position i, it needs a row with at least n - 1 - i trailing zeros. It scans forward from i to find the first row j that qualifies. If no such row exists, it returns -1.

Once a valid row is found at position j, the inner while loop bubbles it up to position i by swapping adjacent entries in the trailing array. Each swap corresponds to one adjacent row swap in the original grid. The total number of swaps accumulates in swaps.

Visual walkthrough

Let's trace through the example grid [[0,0,1],[1,1,0],[1,0,0]] step by step. Watch how the greedy algorithm finds the nearest valid row and bubbles it into place.

The walkthrough shows three key moments. First, row 2 (with 2 trailing zeros) gets bubbled all the way up to position 0, costing 2 swaps. Then the row that landed at position 2 (with 1 trailing zero) gets bubbled up to position 1, costing 1 more swap. The last row automatically satisfies its requirement of 0 trailing zeros. Total: 3 swaps.

Complexity analysis

Time is O(n^2) where n is the number of rows (and columns). Computing trailing zeros takes O(n^2) for the full grid. The greedy placement loop has an outer loop of n iterations. For each iteration, finding the next valid row takes O(n) in the worst case, and bubbling it up also takes O(n). So the placement phase is O(n^2), and the total is O(n^2).

Space is O(n) for the trailing array. You do not need to copy or modify the original grid.

The building blocks

1. Trailing zeros computation

trailing = []
for row in grid:
    count = 0
    for j in range(n - 1, -1, -1):
        if row[j] == 0:
            count += 1
        else:
            break
    trailing.append(count)

This is the dimension reduction step. You scan each row from right to left and count consecutive zeros. The moment you hit a 1, you stop. This pattern of extracting a single summary statistic per row (or column) to reduce a 2D problem to 1D comes up frequently. You will see it in problems like "Maximal Rectangle" (column heights) and "Search a 2D Matrix" (row-level binary search).

2. Greedy selection with bubble swap

for i in range(n):
    need = n - 1 - i
    j = i
    while j < n and trailing[j] < need:
        j += 1
    if j == n:
        return -1
    while j > i:
        trailing[j], trailing[j - 1] = trailing[j - 1], trailing[j]
        j -= 1
        swaps += 1

This is the core greedy loop. For each position, find the nearest valid candidate and bubble it into place with adjacent swaps. The "adjacent swap" constraint is key: you cannot jump a row directly to its target position, you must swap through every row in between. This is the same mechanic as counting inversions in a permutation or computing the minimum number of adjacent swaps to sort an array. The greedy choice of picking the nearest valid row ensures you never do unnecessary work.

Edge cases

• Already valid: if the grid already has all zeros above the diagonal, trailing[i] >= n - 1 - i for every row. No swaps needed, return 0.
• Impossible configuration: if any required trailing zero count cannot be satisfied by any remaining row, return -1. For example, a grid where every row has a 1 in the last column means no row has any trailing zeros, and only position n - 1 can be filled.
• All zeros: every row has n trailing zeros, so the grid is already valid. Return 0.
• Single row: a 1x1 grid always satisfies the constraint. Return 0.
• Multiple rows with the same trailing zero count: the greedy approach handles ties naturally by picking the nearest one, which is always optimal for minimizing bubble swaps.

From understanding to recall

You now understand the two-step structure: reduce the grid to trailing zero counts, then greedily place rows with a bubble-up strategy. The logic is clean, but the details matter. Do you scan for the nearest valid row or the best valid row? Do you bubble up or down? What do you return when no row qualifies?

These are the details that slip away under pressure. Spaced repetition locks them in. You practice writing the trailing zeros computation from memory, then the greedy bubble loop, at increasing intervals. After a few rounds, the entire algorithm is automatic. You see "minimum swaps" and "binary grid" in a problem statement, and the trailing zeros reduction is the first thing you reach for.

Related posts

• Set Matrix Zeroes - Another matrix manipulation problem requiring careful in-place operations
• Sort Colors - Greedy swapping pattern applied to array partitioning
• Jump Game - Greedy forward scanning with a similar "find the farthest reachable" flavor

CodeBricks breaks Minimum Swaps to Arrange a Binary Grid into its trailing zeros reduction and greedy bubble-swap building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy matrix problem shows up in your interview, you do not hesitate. You just write it.