0879MediumArrayGreedyMatrix

Row Shuffles to Clear the Diagonal

Tracked in this browser only

Trains the technique from

LeetCode 1536Minimum Swaps to Arrange a Binary Grid

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A stencil sheet is a square grid of 0s and 1s given as grid, with n rows and n columns.

One shuffle swaps two rows that sit next to each other. The sheet is usable when every cell strictly above the main diagonal holds a 0, that is when grid[i][j] is 0 for every j greater than i.

Return the fewest shuffles that make the sheet usable, or -1 when no number of shuffles can. A shuffle count is never negative, so -1 can only mean it is impossible.

Examples

Example 1

Input: grid = [[0, 0, 0], [1, 1, 0], [1, 0, 0]]
Output: 0

The top row already has the two trailing zeros it needs. The second row needs one trailing zero and ends in a 1, so the third row is brought up past it.

Example 2

Input: grid = [[0, 1], [0, 1]]
Output: -1

Both rows end in a 1, so neither can sit on top where a trailing zero is needed, and no shuffle helps.

Example 3

Input: grid = [[0, 0], [0, 0]]
Output: 0

Every cell above the diagonal already holds a 0, so the sheet is usable as it stands.

Constraints

1 <= grid.length <= 200
Every row of grid has length grid.length
0 <= grid[i][j] <= 1

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def row_shuffles(grid: list[list[int]]) -> int:

Java

public int rowShuffles(int[][] grid)

The intended approach

Time O(n^2) for an n by n sheet: one scan per row position.Space O(n) for the reaches.

A row is only ever moved as a whole, so what matters about it is how many zeros trail its last `1`; call that its reach. Row `i` of a usable sheet needs a reach of at least `n - 1 - i`. Fill the rows from the top down, and for each take the nearest row below that is good enough, bubbling it up one shuffle at a time. Taking the nearest such row is never worse, because any row skipped over has a smaller reach and so is still available for a later, less demanding position, while moving it up costs one shuffle per row it passes. If no row below is good enough, the sheet cannot be made usable.

Pythonentry point: row_shuffles

def row_shuffles(grid):
    n = len(grid)
    reach = []
    for row in grid:
        run = 0
        for c in range(n - 1, -1, -1):
            if row[c] == 1:
                break
            run += 1
        reach.append(run)
    swaps = 0
    for i in range(n):
        need = n - 1 - i
        found = -1
        for j in range(i, n):
            if reach[j] >= need:
                found = j
                break
        if found < 0:
            return -1
        # bubble it up into place, one neighbouring swap at a time
        for j in range(found, i, -1):
            reach[j], reach[j - 1] = reach[j - 1], reach[j]
            swaps += 1
    return swaps

The obvious version

Search outward over row orderings, one neighbouring swap at a time, keeping the orderings already reached, and report how many rounds it takes to reach one that is usable. Explores every swap rather than choosing which row to bring up.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_row_shuffles(grid):
    n = len(grid)

    def usable(order):
        for i in range(n):
            row = grid[order[i]]
            for j in range(i + 1, n):
                if row[j] != 0:
                    return False
        return True

    start = tuple(range(n))
    if usable(start):
        return 0
    seen = {start}
    frontier = [start]
    steps = 0
    while frontier:
        steps += 1
        nxt = []
        for state in frontier:
            for a in range(n - 1):
                lst = list(state)
                lst[a], lst[a + 1] = lst[a + 1], lst[a]
                cand = tuple(lst)
                if cand in seen:
                    continue
                if usable(cand):
                    return steps
                seen.add(cand)
                nxt.append(cand)
        frontier = nxt
    return -1

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in