#778

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Swim in Rising Water

Solve the problem of swimming through a grid of rising water with a binary search on the valid answer space.

array binary search depth first search breadth first search union find

Problem Statement

You are given an n x n integer matrix grid, where each value represents the elevation at a specific point. Water rises gradually over time, and at time t, the water level is t, meaning any cell with elevation less than or equal to t is submerged. You are tasked with swimming from the top-left corner of the grid to the bottom-right corner, where you can only move to neighboring cells with a height less than or equal to t.

The challenge is to determine the earliest time when it is possible to swim from the top-left corner to the bottom-right corner, considering that you can swim in 4-directionally adjacent squares. The problem can be solved by leveraging binary search over the time dimension and using depth-first search (DFS) or breadth-first search (BFS) to check connectivity at each time step.

Examples

Example 1

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

Output: 3

At time 0, you are in grid location (0, 0). You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0. You cannot reach point (1, 1) until time 3. When the depth of water is 3, we can swim anywhere inside the grid.

Example 2

Input: 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]]

Output: 16

The final route is shown. We need to wait until time 16 so that (0, 0) and (4, 4) are connected.

Constraints

n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n2
Each value grid[i][j] is unique.

Solution Approach

Binary Search on Time

Use binary search over the time space from 0 to n^2-1. At each time step, check if the path between the start and end points is traversable given the constraints on water elevation. This approach reduces the problem's complexity by narrowing down the range of valid times.

Graph Traversal for Connectivity Check

At each binary search step, perform a graph traversal using DFS or BFS to check if it's possible to reach the bottom-right corner from the top-left corner. This ensures that the algorithm efficiently checks whether the grid is traversable at each time.

Optimal Time Selection

The key to solving this problem is selecting the optimal time where connectivity is possible. Once the binary search converges, you have the minimum time at which a path exists, making the solution efficient.

Complexity Analysis

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

The time complexity is dominated by the binary search, which runs in O(log n^2), and each graph traversal at each time step, which is O(n^2). The overall complexity is O(n^2 log n). The space complexity depends on the implementation of the graph traversal algorithm, typically O(n^2) for storing visited nodes in the grid.

What Interviewers Usually Probe

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

Common Pitfalls or Variants

Common pitfalls

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

Follow-up variants

The grid size can vary, and candidates should be able to adapt the solution for both small and larger grids, maintaining efficiency.
Grids with uniform elevation or with extreme differences in elevation at specific points could require additional considerations for optimization.
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.

FAQ

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.

terminal

Solution

Solution 1: Union Find

We can map each position $(i, j)$ to an ID $id = i \times n + j$, and use a union-find data structure to maintain connected components.

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 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

Continue Practicing

#1631 path with minimum effort #827 making a large island #695 max area of island