What is the key to solving the 'Swim in Rising Water' problem?

The key is using binary search over the time space and checking connectivity using a graph traversal algorithm like DFS or BFS.

Can I use Dijkstra's algorithm to solve this problem?

Yes, Dijkstra's algorithm can be used to check for the shortest path at each time step, but binary search with DFS/BFS is typically more efficient for this problem.

How do I handle edge cases in 'Swim in Rising Water'?

Edge cases include very small grids, grids with minimal elevation differences, and cases where the water rises very quickly. Make sure your algorithm handles boundary conditions properly.

What is the complexity of the solution?

The time complexity is O(n^2 log n) and space complexity is typically O(n^2), depending on the traversal algorithm used.

What graph traversal algorithm is best for this problem?

Both DFS and BFS are effective, but BFS may be slightly more intuitive for checking connectivity, especially when combined with binary search.

#778

Hard

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

LeetCode 题解工作台

水位上升的泳池中游泳

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认…

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

题目描述

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。

当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。

你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间。

示例 1:

输入: grid = [[0,2],[1,3]]
输出: 3
解释:
时间为0时，你位于坐标方格的位置为 (0, 0)。
此时你不能游向任意方向，因为四个相邻方向平台的高度都大于当前时间为 0 时的水位。
等时间到达 3 时，你才可以游向平台 (1, 1). 因为此时的水位是 3，坐标方格中的平台没有比水位 3 更高的，所以你可以游向坐标方格中的任意位置

示例 2:

输入: grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
输出: 16
解释: 最终的路线用加粗进行了标记。
我们必须等到时间为 16，此时才能保证平台 (0, 0) 和 (4, 4) 是连通的

提示:

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n²
grid[i][j] 中每个值 均无重复

lightbulb

解题思路

方法一：并查集

我们可以将每个位置 $(i, j)$ 映射为一个编号 $id = i \times n + j$ ，并使用并查集维护连通分量。

我们首先用一个一维数组 $hi$ 记录每个高度对应的位置编号，即 $hi[h]$ 表示高度为 $h$ 的位置编号。

然后我们从高度 $0$ 开始遍历到高度 $n^2 - 1$ ，对于每个高度 $t$ ，我们将位置 $hi[t]$ 与其四个相邻且高度不超过 $t$ 的位置进行合并。如果合并后，位置 $0$ 和位置 $n^2 - 1$ 连通了，那么我们就找到了最小的时间 $t$ ，返回 $t$ 即可。

时间复杂度 $O(n^2 \times \log n)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是矩阵的边长。

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        n = len(grid)
        m = n * n
        p = list(range(m))
        hi = [0] * m
        for i, row in enumerate(grid):
            for j, h in enumerate(row):
                hi[h] = i * n + j
        dirs = (-1, 0, 1, 0, -1)
        for t in range(m):
            x, y = divmod(hi[t], n)
            for dx, dy in pairwise(dirs):
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] <= t:
                    p[find(x * n + y)] = find(nx * n + ny)
            if find(0) == find(m - 1):
                return t
        return 0

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
Candidates should be able to describe the binary search strategy effectively and demonstrate understanding of how it applies to this problem.
question_mark
Look for candidates who can explain the relationship between binary search and graph traversal clearly, particularly in terms of time complexity reduction.
question_mark
Candidates should mention graph traversal techniques like DFS or BFS and be able to select the appropriate one based on problem constraints.

warning

常见陷阱

外企场景

error
Candidates might struggle with understanding the relationship between binary search and graph traversal, leading to inefficient solutions.
error
Failing to correctly handle grid boundaries and elevation constraints during traversal can result in incorrect or incomplete solutions.
error
Candidates may overlook edge cases such as very small grids or grids with minimal differences in elevation, where water might rise slower.

swap_horiz

进阶变体

外企场景

arrow_right_alt
The grid size can vary, and candidates should be able to adapt the solution for both small and larger grids, maintaining efficiency.
arrow_right_alt
Grids with uniform elevation or with extreme differences in elevation at specific points could require additional considerations for optimization.
arrow_right_alt
The problem could be modified to account for other movement rules (e.g., diagonal movement) or changing grid dimensions, which would require adjustments to both the binary search and graph traversal approach.

help

常见问题

外企场景

继续练习

#1631 最小体力消耗路径 #827 最大人工岛 #695 岛屿的最大面积