#1536

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Swaps to Arrange a Binary Grid

Compute the minimum number of adjacent row swaps to transform a binary grid so all upper-triangle cells are zero using a greedy approach.

array greedy matrix

Problem Statement

You are given an n x n binary grid where each element is 0 or 1. In one step, you can swap any two adjacent rows of the grid. A grid is valid if, for every row i, all elements grid[i][j] are zero when j > i, meaning all cells above the main diagonal are zeros.

Return the minimum number of steps needed to make the grid valid. If it is impossible to achieve a valid grid with adjacent row swaps, return -1. For example, given grid = [[0,0,1],[1,1,0],[1,0,0]], the minimum number of swaps is 3, whereas a grid like [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]] cannot be made valid and should return -1.

Examples

Example 1

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

Output: 3

Example details omitted.

Example 2

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

Output: -1

All rows are similar, swaps have no effect on the grid.

Example 3

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

Output: 0

Example details omitted.

Constraints

n == grid.length == grid[i].length
1 <= n <= 200
grid[i][j] is either 0 or 1

Solution Approach

Compute the rightmost 1 for each row

For each row, find the index of the rightmost 1. This transforms the matrix into an array maxRight where maxRight[i] represents the last 1 in row i. This allows greedy identification of which rows must be moved to satisfy the invariant above the main diagonal.

Greedy swapping to enforce validity

Iterate through rows top-down. For row i, find the first row j ≥ i where maxRight[j] ≤ i. Swap adjacent rows downward until row j reaches position i, incrementing the swap counter. This ensures each row satisfies the condition without unnecessary rearrangements.

Early termination if impossible

If no suitable row j exists for position i such that maxRight[j] ≤ i, the grid cannot be made valid. Immediately return -1. This prevents wasted computation and handles the primary failure mode of identical rows or blocked 1s.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) due to scanning each row and performing at most n swaps per row. Space complexity is O(n) to store the maxRight array, representing the last 1 in each row, without modifying the original grid.

What Interviewers Usually Probe

Looking for a clear greedy strategy tied to maxRight positions.
Expect correct handling of impossible grids returning -1.
Assessing whether swaps are minimized without unnecessary movements.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check if no row can satisfy maxRight ≤ i, causing incorrect results.
Swapping rows non-adjacently rather than only adjacent rows.
Miscomputing rightmost 1 leading to wrong row selection and extra swaps.

Follow-up variants

Compute minimum swaps for a triangular subgrid instead of full matrix.
Allow swapping any rows, not just adjacent ones, changing the greedy logic.
Find the maximum number of rows already valid before any swaps are required.

FAQ

What is the main strategy for Minimum Swaps to Arrange a Binary Grid?

The primary strategy is a greedy approach using the rightmost 1 in each row to guide adjacent row swaps efficiently.

How do I determine if the grid can be made valid?

Check if, for each row, there exists a row below with maxRight ≤ current index; if not, return -1 immediately.

Can I swap non-adjacent rows?

No, only adjacent row swaps are allowed; the solution must incrementally move rows downward to the correct position.

What is the time complexity of the greedy solution?

Time complexity is O(n^2) because each row may require scanning and moving up to n rows, and space complexity is O(n) for the maxRight array.

How does the maxRight array help in this problem?

It captures the last 1 in each row, allowing the greedy algorithm to determine which rows can be moved to satisfy the zero-above-diagonal invariant efficiently.

terminal

Solution

Solution 1: Greedy

We process row by row. For the $i$-th row, the position of the last '1' must be less than or equal to $i$. We find the first row that meets the condition in $[i, n)$, denoted as $k$. Then, starting from the $k$-th row, we swap the adjacent two rows upwards until the $i$-th row.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def minSwaps(self, grid: List[List[int]]) -> int:
        n = len(grid)
        pos = [-1] * n
        for i in range(n):
            for j in range(n - 1, -1, -1):
                if grid[i][j] == 1:
                    pos[i] = j
                    break
        ans = 0
        for i in range(n):
            k = -1
            for j in range(i, n):
                if pos[j] <= i:
                    ans += j - i
                    k = j
                    break
            if k == -1:
                return -1
            while k > i:
                pos[k], pos[k - 1] = pos[k - 1], pos[k]
                k -= 1
        return ans

Continue Practicing

#1605 find valid matrix given row and column sums #1727 largest submatrix with rearrangements #1253 reconstruct a 2 row binary matrix