Swim in Rising Water

Swim in Rising Water looks like a water-physics puzzle, but it is really a shortest-path problem in disguise. The twist: instead of adding up costs along a path, we take the maximum — and that one change turns Dijkstra into the perfect tool.

The slow way first

You could binary-search the answer: pick a time t, then run a flood-fill to ask "can I reach the goal using only cells with elevation ≤ t?" That works and is a fine answer, but it reruns a full search for every candidate t.

The cleaner question: along any path, what number actually matters? Not the sum of elevations — only the single highest cell you are forced to cross. So we want the path that minimizes its maximum cell. That is exactly the shape Dijkstra solves, if we redefine "path cost" as max instead of sum.

The idea: Dijkstra with a max instead of a sum

Run Dijkstra from the top-left. Keep a min-heap of frontier cells, each keyed by the largest elevation on the best path that reaches it so far. Pop the smallest such key, mark the cell visited, and push its unvisited neighbors with an updated running max. The first time we pop the bottom-right, its key is the answer.

Why does popping the goal end it? A min-heap always hands back the smallest key first, so the moment the goal surfaces, no cheaper path to it can still exist. In the example, the goal pops at max 2 while the elevation-4 cell is still sitting unused in the heap.

Walk through it

Step through the animation. Cells turn visited as they pop off the heap. Watch the running max in the side panel: it climbs to 2 and then stays there, because every cell on the winning path is ≤ 2. The expensive 4 cell never gets visited at all — Dijkstra reaches the goal before it ever becomes the cheapest option.

Pseudocode

heap = [(grid[0][0], 0, 0)]      # (max elevation so far, row, col)
seen = {(0, 0)}
while heap is not empty:
    t, r, c = pop smallest from heap
    if (r, c) is the bottom-right cell:
        return t                  # answer = max cell on the best path
    for each in-bounds neighbor (nr, nc) not in seen:
        add (nr, nc) to seen
        push (max(t, grid[nr][nc]), nr, nc) onto the heap

The Python solution

def swim_in_water(grid):
    n = len(grid)
    pq = [(grid[0][0], 0, 0)]   # (max so far, r, c)
    seen = {(0, 0)}
    while pq:
        t, r, c = heapq.heappop(pq)
        if (r, c) == (n - 1, n - 1):
            return t
        for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            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(pq, (max(t, grid[nr][nc]), nr, nc))

• pq is a min-heap of (max-so-far, row, col). Python orders tuples by their first element, so the smallest running max always pops first.
• We seed it with the start cell and add (0, 0) to seen immediately, so we never push it again.
• Lines 6-8 are the heart: pop the cheapest frontier cell, and if it is the goal, that running max is the answer.
• For each in-bounds, unvisited neighbor we push max(t, grid[nr][nc]) — the path cost can only rise to clear a taller cell, never fall.
• Marking a cell seen at push time keeps each cell on the heap once, which is what makes the loop terminate.

Complexity

There are n² cells; each is pushed and popped at most once, and every heap operation is O(log n²) = O(log n). The seen set and heap together use O(n²) space. Same big-O as binary search, but a single clean pass instead of repeated searches.

When this pattern shows up

Practice