How does binary search help in solving the Last Day Where You Can Still Cross problem?

Binary search allows us to optimize the search for the last possible day to cross the matrix, reducing the number of days we need to check.

Can I use DFS instead of BFS for the Last Day Where You Can Still Cross problem?

Yes, DFS can be used instead of BFS to explore paths through the matrix. Both methods work, but BFS may be more space-efficient in this case.

What happens if I don't use binary search to narrow down the days?

Without binary search, you'd need to check every single day for a valid path, resulting in much higher time complexity.

How can I ensure my BFS or DFS is efficient for large matrices?

You can ensure efficiency by optimizing the path validation process, using visited nodes and limiting the search space to only land cells.

What are the key graph algorithms used in the Last Day Where You Can Still Cross problem?

The key algorithms are BFS or DFS for path validation and binary search for narrowing down the possible days.

#1970

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

你能穿过矩阵的最后一天

给你一个下标从 1 开始的二进制矩阵，其中 0 表示陆地， 1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。一开始在第 0 天，整个矩阵都是陆地。但每一天都会有一块新陆地被水淹没变成水域。给你一个下标从 1 开始的二维数组 cells ，其中 cells[i] …

数组二分查找深度优先搜索广度优先搜索并查集

题目描述

给你一个下标从 1 开始的二进制矩阵，其中 0 表示陆地，1 表示水域。同时给你 row 和 col 分别表示矩阵中行和列的数目。

一开始在第 0 天，整个矩阵都是陆地。但每一天都会有一块新陆地被水淹没变成水域。给你一个下标从 1 开始的二维数组 cells ，其中 cells[i] = [r_i, c_i] 表示在第 i 天，第 r_i 行 c_i 列（下标都是从 1 开始）的陆地会变成水域（也就是 0 变成 1 ）。

你想知道从矩阵最上面一行走到最下面一行，且只经过陆地格子的 最后一天 是哪一天。你可以从最上面一行的任意格子出发，到达最下面一行的任意格子。你只能沿着四个基本方向移动（也就是上下左右）。

请返回只经过陆地格子能从最上面一行走到最下面一行的 最后一天 。

示例 1：

输入：row = 2, col = 2, cells = [[1,1],[2,1],[1,2],[2,2]]
输出：2
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 2 天。

示例 2：

输入：row = 2, col = 2, cells = [[1,1],[1,2],[2,1],[2,2]]
输出：1
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 1 天。

示例 3：

输入：row = 3, col = 3, cells = [[1,2],[2,1],[3,3],[2,2],[1,1],[1,3],[2,3],[3,2],[3,1]]
输出：3
解释：上图描述了矩阵从第 0 天开始是如何变化的。
可以从最上面一行到最下面一行的最后一天是第 3 天。

提示：

2 <= row, col <= 2 * 10⁴
4 <= row * col <= 2 * 10⁴
cells.length == row * col
1 <= r_i <= row
1 <= c_i <= col
cells 中的所有格子坐标都是唯一的。

lightbulb

解题思路

方法一：二分查找 + BFS

我们注意到，如果我们能在第 $k$ 天从最上面一行走到最下面一行，那么对于任意 $0 \lt k' \lt k$ ，我们也能在第 $k'$ 天从最上面一行走到最下面一行。这存在着单调性，因此，我们可以使用二分查找，找到最大的 $k$ ，使得我们能在第 $k$ 天从最上面一行走到最下面一行。

我们定义二分查找的左边界 $l = 1$ ，右边界 $r = |cells|$ ，其中 $|cells|$ 表示数组 $cells$ 的长度。然后，我们二分枚举 $k$ ，对于每一个 $k$ ，我们取 $\textit{cells}$ 的前 $k$ 个元素，将这些元素对应的格子变成水域，然后使用广度优先搜索，从最上面一行开始，尝试走到最下面一行。如果我们能走到最下面一行，那么说明我们可以在第 $k$ 天从最上面一行走到最下面一行，我们就将左边界 $l$ 更新为 $k$ ，否则，我们将右边界 $r$ 更新为 $k - 1$ 。

时间复杂度 $O(m \times n \times \log (m \times n))$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $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

25

26

27

28

class Solution:
    def latestDayToCross(self, row: int, col: int, cells: List[List[int]]) -> int:
        def check(k: int) -> bool:
            g = [[0] * col for _ in range(row)]
            for i, j in cells[:k]:
                g[i - 1][j - 1] = 1
            q = [(0, j) for j in range(col) if g[0][j] == 0]
            for x, y in q:
                if x == row - 1:
                    return True
                for a, b in pairwise(dirs):
                    nx, ny = x + a, y + b
                    if 0 <= nx < row and 0 <= ny < col and g[nx][ny] == 0:
                        q.append((nx, ny))
                        g[nx][ny] = 1
            return False

        n = row * col
        l, r = 1, n
        dirs = (-1, 0, 1, 0, -1)
        while l < r:
            mid = (l + r + 1) >> 1
            if check(mid):
                l = mid
            else:
                r = mid - 1
        return l

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates an understanding of binary search and how to apply it to a range of possible answers.
question_mark
Candidate applies BFS/DFS to verify paths through a grid, indicating solid knowledge of graph traversal algorithms.
question_mark
Candidate identifies optimization opportunities through binary search, showing problem-solving skills in narrowing down search spaces.

warning

常见陷阱

外企场景

error
Failing to optimize the search space by not using binary search on the valid days.
error
Incorrect path validation by using inefficient graph traversal techniques or not accounting for the matrix's changing state over days.
error
Overcomplicating the solution with unnecessary checks or missing edge cases like when the matrix is fully flooded.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Use Union-Find to handle connectivity checks across the matrix during water flooding.
arrow_right_alt
Apply dynamic programming or memoization to speed up the path search process for each day.
arrow_right_alt
Solve the problem by iterating through all days and performing BFS/DFS for each day, though less optimal than binary search.

help

常见问题

外企场景

继续练习

#1631 最小体力消耗路径 #1905 统计子岛屿 #778 水位上升的泳池中游泳