Show problems as
Classic problem #1536MediumArrayGreedyMatrix

Minimum Swaps to Arrange a Binary Grid

Real-world version: Row Shuffles to Clear the Diagonal
Tracked in this browser only
Read Minimum Swaps to Arrange a Binary Grid on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def row_shuffles(grid: list[list[int]]) -> int:
Java
public int rowShuffles(int[][] grid)

More on the same topics