Swim in Rising Water (LeetCode 778)

The problem

You get an n × n grid where grid[r][c] is the elevation of that cell; the values are a permutation of 0 to n² − 1. At time t the water level everywhere is t, and you can move between adjacent cells (up, down, left, right) if both have elevation at most t. Moving takes no time. Return the earliest time you can get from the top-left cell to the bottom-right.

Input:
0 2
1 3

Output: 3

You can’t reach the bottom-right cell until the water covers it at time 3. By then the path 0 → 1 → 3 is open.

How to think about it

Start with brute force. For each time t = 0, 1, 2, …, run a BFS that only steps on cells with elevation at most t, and stop at the first t where the target is reachable. That is O(n²) times per BFS and up to n² values of t: O(n⁴). Binary search on t cuts it to O(n² log n), which is a fine answer too.

Reframe the cost. You can cross a path once the water has risen past every cell on it. So the time for a given path is the maximum elevation along it. You want the path whose maximum is smallest: a minimax path, just like Path With Minimum Effort.

The key insight: Dijkstra with max as the combine step. Keep a min-heap of (time, r, c), where time is the highest cell seen on the best route to that cell. Always expand the cell with the lowest such time. Reaching a neighbour costs max(t, grid[nr][nc]). Because max never decreases along a path, the first time the target is popped, its time is optimal. Each cell’s first push is already its best value here (the heap pops in order and max is monotone), so a simple seen set at push time is enough.

Which pattern is this? Minimax shortest path with Dijkstra. The tell is “the cost of a path is its worst cell”, on a grid with a heap.

Approach

1. Push (grid[0][0], 0, 0) onto a min-heap and mark (0, 0) as seen.
2. Pop the cell with the lowest time t. If it is the bottom-right cell, return t.
3. For each unseen neighbour, mark it seen and push (max(t, grid[nr][nc]), nr, nc).
4. Repeat. The target is always reachable eventually, since the water will rise above everything.

Solution

import heapq
def swimInWater(grid):
    n = len(grid); h = [(grid[0][0], 0, 0)]; seen = {(0, 0)}
    while h:
        t, r, c = heapq.heappop(h)                   # lowest water level reachable next
        if (r, c) == (n - 1, n - 1): return t
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                seen.add((nr, nc)); heapq.heappush(h, (max(t, grid[nr][nc]), nr, nc))  # path cost = highest cell
    return -1
# swimInWater([[0,2],[1,3]]) -> 3

Dry run

On the 2 × 2 example:

The answer is 3. On LeetCode’s larger 5 × 5 spiral example, the same code returns 16.

Complexity

• Time: O(n² log n). Each of the n² cells is pushed once, and each heap operation costs O(log n²) = O(log n).
• Space: O(n²). The heap and the seen set.

Edge cases and pitfalls

• 1 × 1 grid returns grid[0][0]: you must wait for the start cell itself.
• The start cell counts. Seeding the heap with 0 instead of grid[0][0] gives a wrong answer when the start is high.
• Summing elevations solves a different problem. The cost is the max.
• Plain BFS without a heap explores in the wrong order and can return a too-high time.
• Union-find alternative: add cells in increasing elevation and stop when the two corners join. Same complexity, and worth mentioning.

Related problems

• Path With Minimum Effort (LeetCode 1631): the same minimax Dijkstra, on height differences.
• Network Delay Time (LeetCode 743): standard Dijkstra, the template this problem bends.
• Number of Islands (LeetCode 200): grid flood fill, the building block of the binary-search-plus-BFS approach.