Rows Under the Diagonal

Medium

You are given a square n × n grid board of zeros and ones. In one move you may swap two adjacent rows. The grid is valid when every cell strictly above the main diagonal (running from the top-left to the bottom-right corner) is zero. In other words, in row i (0-indexed) every cell from column i + 1 onward must be zero. Return the smallest number of moves that makes the grid valid, or -1 if that is impossible.

Example 1

board=[[1, 1, 0], [1, 0, 0], [0, 1, 1]] → 1

One swap of the first two rows gives [[1, 0, 0], [1, 1, 0], [0, 1, 1]]. The last row may hold anything, since it has no cells above the diagonal.

Example 2

board=[[0, 1], [0, 1]] → -1

Both rows end in 1, but the top row must have a 0 there. The answer is -1.

Example 3

board=[[1]] → 0

Constraints

1 ≤ n ≤ 200
len(board) = len(board[i]) = n
board[i][j] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Matrix

Similar problems

Raise Towers, Keep the Skyline Medium Best Binary Rows After Flips Medium Two Rows of Lamps Medium A Table From Its Totals Medium Biggest Block After a Column Shuffle Medium

Input

board=[[1, 1, 0], [1, 0, 0], [0, 1, 1]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 73 tests on the server, hidden ones included.