LeetCode #778 Hard

Swim in Rising Water

Find the earliest water level at which a path exists from the top-left to bottom-right cell.

graphdijkstramatrix

02

Intuition

Enumerating paths is exponential, while binary-searching time repeats a reachability traversal. A path's cost is not the sum of its cells; it is the maximum elevation encountered. Dijkstra's algorithm still applies when relaxation combines costs with max instead of addition. The first time the destination leaves the min-heap, its smallest possible bottleneck is finalized.

How to spot this pattern

A path objective that minimizes the maximum edge or vertex value is a bottleneck shortest-path problem. Dijkstra works by replacing additive relaxation with the operation that defines the path cost, here max.

03

Approach

1

Treat elevation as a bottleneck path cost

Start with cost grid[0][0]. Moving onto a neighbor changes the route cost to the larger of the current cost and the neighbor's elevation.

2

Expand the lowest known bottleneck first

Keep (cost, row, col) states in a min-heap and ignore stale entries. This ordering ensures no later route can improve a cell after its best cost is popped.

3

Stop when the destination is finalized

Relax four-directional neighbors whenever the candidate bottleneck is smaller than their stored value. Return immediately when the bottom-right cell is popped, because that value is globally minimal.

04

Solution

▶1class Solution:
▶2    def swimInWater(self, grid: List[List[int]]) -> int:
▶3        n = len(grid)
▶4        best = [[float('inf')] * n for _ in range(n)]
▶5        best[0][0] = grid[0][0]
▶6        heap = [(grid[0][0], 0, 0)]
▶7 
▶8        while heap:
▶9            cost, row, col = heappop(heap)
▶10            if cost != best[row][col]:
▶11                continue
▶12            if row == n - 1 and col == n - 1:
▶13                return cost
▶14            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
▶15                nr = row + dr
▶16                nc = col + dc
▶17                if 0 <= nr < n and 0 <= nc < n:
▶18                    candidate = max(cost, grid[nr][nc])
▶19                    if candidate < best[nr][nc]:
▶20                        best[nr][nc] = candidate
▶21                        heappush(heap, (candidate, nr, nc))

05

Common pitfalls

Adding elevations

✗ Wrong

candidate = cost + grid[nr][nc]

✓ Right

candidate = max(cost, grid[nr][nc])

Waiting time is determined by the highest cell, not the sum of elevations.

Returning when the destination is pushed

✗ Wrong

if (nr, nc) == target:
    return candidate

✓ Right

if (row, col) == target:
    return cost

A pushed destination may later receive a smaller bottleneck route.

Marking every discovered cell permanently

✗ Wrong

visited.add((nr, nc))

✓ Right

if candidate < best[nr][nc]:
    best[nr][nc] = candidate

A cell can be discovered first through a worse bottleneck.

06

Edge cases

A 1-by-1 grid

The start is also the destination, so return its elevation.

The geometrically short path crosses a tall cell

Heap ordering can prefer a longer route with a lower maximum elevation.

The starting cell is the highest required elevation

Every route cost begins at that elevation and never decreases.

07

Complexity

Time

O(n^2 log n)

Space

O(n^2)

Each cell can enter the heap after a successful bottleneck relaxation.