Swim in Rising Water — The Flooded Quarry

Boss 4: The Flooded Quarry

Boss 3 gave you Dijkstra: a heap of frontier nodes, pop the cheapest, settle it forever. This boss hands you the exact same weapon and changes one line. The cost of a path is no longer the sum of what you crossed. It's the worst thing you crossed.

That tiny swap has a name, the minimax path, and it's one of the most useful Dijkstra variants in existence. Bottleneck routing, quality-of-service networks, "safest route" problems: they're all this boss wearing different hats.

The story

An abandoned quarry, cut into square terraced platforms, every platform a different height. You're standing on the top-left rim. The way out is the far corner, diagonally across.

Then it starts to rain. Hard.

The quarry floods evenly: when the water level reaches t, every platform of height t or lower is underwater, and you can swim across it to any underwater neighbor, up, down, left, right. Platforms still above the waterline are sheer stone walls, no climbing.

0 1 2
8 7 3
6 5 4

You could wait for the whole quarry to drown, height 8 and all. But you're cold, and you're impatient. Squint at the map: if you wait until the water hits 4, the top row floods (0, 1, 2), then 3, then 4, and you can swim along the rim and down the right edge, never touching the tall stuff in the middle. Wait time: 4. Any earlier and platform 4 still blocks the only route.

That's the game. Least waiting time such that a fully-flooded path exists.

The problem, dressed up properly

You are given an n x n grid where grid[r][c] is the elevation of that cell, all elevations distinct. Rain raises the water level: at time t, every cell with elevation at most t is underwater. You can swim between 4-directionally adjacent cells if both are underwater. Return the least time at which you can travel from (0, 0) to (n - 1, n - 1).

LeetCode 778, "Swim in Rising Water". Hard-rated, and the cleanest possible showcase of what Dijkstra actually proves.

The naive attempt

Simulate the rain. Try t = 0, 1, 2, ... and run a fresh BFS at each water level:

from collections import deque
 
def swim_in_water(grid):
    n = len(grid)
    t = 0
    while True:
        if grid[0][0] <= t:                    # can we even enter?
            seen = {(0, 0)}
            queue = deque([(0, 0)])
            while queue:
                r, c = queue.popleft()
                if (r, c) == (n - 1, 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 and grid[nr][nc] <= t:
                        seen.add((nr, nc))
                        queue.append((nr, nc))
        t += 1

It works. It's also embarrassing. Elevations go up to n² - 1, so that's up to n² BFS runs of O(n²) each, O(n⁴)-ish, and every BFS re-discovers almost everything the previous one already knew. The water rises one unit and we flood the whole map from scratch.

Two smarter families exist. Binary search on t with one BFS per guess, the "binary search the answer" move from Koko back in Dungeon 4, gets you O(n² log n). Union-Find, sinking cells in elevation order and merging them with underwater neighbors until the two corners share a component, also lands O(n² log n). Both are fine. But the cleanest version doesn't guess the answer or sort the cells. It grows the answer directly.

The weapon: Dijkstra, with max instead of plus

Reframe the question. Any route from corner to corner gets blocked by exactly one thing: its tallest platform. Wait time for that route = the max elevation along it. So the answer is:

Over all paths, minimize the maximum cell.

That's a shortest-path problem where the "length" of a path is its worst cell, not its sum. And here's the beautiful part: Dijkstra doesn't care. Dijkstra's settle argument, "the cheapest thing in the heap can never be improved later", only needs one property: path cost never decreases as the path grows. Adding a positive edge to a sum can't shrink the sum. Taking max with one more cell can't shrink the max. Same monotone shape, same proof, same code, one line changed:

new_cost = max(cost, elevation)     # Boss 3 wrote: cost + edge_weight

The grid is a graph exactly the way Dungeon 11 taught with Number of Islands: cells are nodes, 4-neighbors are edges. Pop the frontier cell with the smallest bottleneck-so-far. The first time the far corner pops, its bottleneck is the answer.

import heapq
 
def swim_in_water(grid: list[list[int]]) -> int:
    n = len(grid)
    heap = [(grid[0][0], 0, 0)]        # (bottleneck so far, row, col)
    seen = {(0, 0)}
    while heap:
        bottleneck, r, c = heapq.heappop(heap)
        if r == n - 1 and c == n - 1:
            return bottleneck
        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))
                heapq.heappush(heap, (max(bottleneck, grid[nr][nc]), nr, nc))

Water spreading through a quarry, popping the lowest reachable platform first. The algorithm is the rain.

Watching it work

The classic warm-up grid first: [[0, 2], [1, 3]]. Start at 0. Push neighbors: right costs max(0, 2) = 2, down costs max(0, 1) = 1. Pop the 1, push its neighbor: max(1, 3) = 3. Pop the 2, its unseen neighbor also lands at max(2, 3) = 3. Pop 3, and that's the far corner. Answer: 3. Both routes pass through the height-3 cell, so no cleverness could beat it.

Now the quarry from the story:

0 1 2
8 7 3
6 5 4

Answer: 4, exactly the hand-squinted route along the rim. Notice what never happened: the 8, the 7, the 6, the 5 sat in (or out of) the heap untouched. The heap kept steering around the tall stone because tall stone is expensive, and expensive things sink to the back of a min-heap.

Gotchas

1. Seeding the heap with 0 instead of grid[0][0]. The start cell has a height too. If grid[0][0] is 7, you stand on the rim until the water reaches 7, you don't get to be underwater for free just because you started there. Seed with (grid[0][0], 0, 0) or every answer on grids with a tall start cell comes out low.

2. Writing bottleneck + grid[nr][nc] on reflex. Muscle memory from Boss 3 is real. The plus version compiles, runs, and returns a confidently wrong number, sum of elevations along some path, which answers nothing anyone asked. If your answer looks suspiciously huge, this is the first place to look.

3. Fumbling the visited-at-push vs visited-at-pop choice. This code marks cells seen at push time. In general Dijkstra that's a known trap, because a cheaper route to a pushed-but-unpopped node can appear later. Here it's safe: the cost into a cell is max(bottleneck, its own elevation), and since pops come off the heap in nondecreasing order, any later route arrives with an equal-or-worse bottleneck, so the first push is already the best. If that argument makes you nervous, mark at pop and skip already-settled cells; it's still correct, the heap just holds a few duplicates.

4. Building cleverness on "all elevations are distinct". The guarantee is flavor, not structure. It makes the story tidy, one platform sinks per tick, but the algorithm never uses it. Ties in the heap resolve arbitrarily and the answer is unchanged. If your solution needs distinctness, you've solved a different problem.

Complexity

n² cells, each pushed and popped a constant number of times, each heap operation costing the log of the heap size.

Time: O(n² log n). Space: O(n²) for the heap and the seen set.

The naive rain simulation was O(n⁴)-ish. Binary search plus BFS ties the heap at O(n² log n), and Union-Find matches it too. The heap wins on elegance: no guessing, no sorting, the answer grows out of the start cell like the flood itself.

Boss down

You push off the rim at the exact minute the last platform on your route slips underwater, swim the cold corridor along the rim, and haul yourself out at the far corner. Behind you the quarry keeps filling, but you're already gone.

Take the reframe with you: the cost of a path is whatever the problem says it is. Sum, max, min, product, and Dijkstra survives every swap that stays monotone. One-line changes to old weapons are how late dungeons get cleared.

Boss 5 is Alien Dictionary — The Lost Alphabet. Topological sort returns from Dungeon 11's epilogue, but with a cruel twist: nobody hands you the graph this time. All you get is a list of words, already sorted by an alphabet no human has seen, and you must reverse-engineer the letter ordering from how the words compare. Build the graph first, then sort it. Bring a notebook.