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.

#1536

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

排布二进制网格的最少交换次数

给你一个 n x n 的二进制网格 grid ，每一次操作中，你可以选择网格的相邻两行进行交换。一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1 。主对角线指的是从 (1, 1) 到 (n, n) 的这…

数组贪心矩阵

题目描述

给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的 相邻两行 进行交换。

一个符合要求的网格需要满足主对角线以上的格子全部都是 0 。

请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1 。

主对角线指的是从 (1, 1) 到 (n, n) 的这些格子。

示例 1：

输入：grid = [[0,0,1],[1,1,0],[1,0,0]]
输出：3

示例 2：

输入：grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
输出：-1
解释：所有行都是一样的，交换相邻行无法使网格符合要求。

示例 3：

输入：grid = [[1,0,0],[1,1,0],[1,1,1]]
输出：0

提示：

n == grid.length
n == grid[i].length
1 <= n <= 200
grid[i][j] 要么是 0 要么是 1 。

lightbulb

解题思路

方法一：贪心

我们逐行处理，对于第 $i$ 行，最后一个 $1$ 所在的位置必须小于等于 $i$ ，我们在 $[i, n)$ 中找到第一个满足条件的行，记为 $k$ 。然后从第 $k$ 行开始，依次向上交换相邻的两行，直到第 $i$ 行。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是网格的边长。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#1605 给定行和列的和求可行矩阵 #1727 重新排列后的最大子矩阵 #1253 重构 2 行二进制矩阵