Swim in Rising Water

from heapq import heappush, heappop
def swim_in_water(grid):
    n = len(grid)
    heap, seen = [(grid[0][0], 0, 0)], {(0, 0)}
    while heap:
        t, r, c = heappop(heap)
        if r == c == n - 1:
            return t
        for nr, nc in (r+1, c), (r-1, c), (r, c+1), (r, c-1):
            if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
                seen.add((nr, nc))
                heappush(heap, (max(t, grid[nr][nc]), nr, nc))

Swim in Rising Water. In an n by n grid of heights, at time t the water is t deep, and you can swim between neighbors that are both at most t. Find the least time from top left to bottom right.

For zero, two, one, three, the corner is three high: answer three. In the five by five spiral, the path stays blocked until the water hits sixteen.

The direct way: for each time t, flood fill and check the corner. Here, seventeen fills. That's n squared fills of n squared cells: n to the fourth.

The key idea: a path costs its highest cell, not the sum. The top route adds up to less, but climbs to eight. The left one stays at six. So run Dijkstra with a min heap keyed by the highest cell so far. When the corner pops, its key is the answer. It's Network Delay Time, with max instead of plus.

In code, the heap starts at the top left. Pop the smallest key. At the corner, return it. Otherwise, push each new neighbor with the larger of the key and its height.

On the spiral, zero to five pop in order. Then the lowest edge cell is sixteen; the twenties wait. Past sixteen, every cell is lower, so the key stays sixteen to the corner.

Each cell is pushed once: n squared log n time, n squared space. Binary search on time, or union find by height, also works.

Lowest cell first, keep the highest, stop at the corner. That's Swim in Rising Water.