Pattern visualizer

Swim in Rising Water

Reframe the rising water as a single number per cell — its elevation — and the question becomes: what is the smallest value T such that a path from start to target uses only cells with elevation <= T? That is a minimax path, and it has the same greedy structure as Dijkstra: always expand the lowest elevation not yet visited. The running maximum elevation seen so far can only grow as the search proceeds, so the instant the target is popped, that running maximum IS the answer — nothing cheaper could have reached it first. Animated on: A 3x3 elevation grid, water rising one level per day, swimming allowed only between adjacent cells both at or below the current water level — what is the minimum water level that connects (0,0) to (2,2)?.

Dijkstra-style minimax: always pop the lowest unvisited elevation

time O(n^2 log n)space O(n^2)step 1 / 10

Badge = cell elevation

line 1

Water starts at level 0 and rises by 1 each day; you can swim between two adjacent cells only once BOTH are at or below the current water level. The question is the lowest water level at which a path of adjacent, already-submerged cells connects (0,0) to (2,2).

Pseudocode

1FUNCTION swimInWater(grid, n):
2  discovered <- SET containing (0, 0)
3  heap <- MIN-HEAP with (grid[0][0], 0, 0)
4  ans <- 0
5  WHILE heap NOT EMPTY
6    (elev, r, c) <- POP-MIN(heap)
7    ans <- MAX(ans, elev)
8    IF r = n - 1 AND c = n - 1
9      RETURN ans
10    FOR EACH (nr, nc) IN NEIGHBORS(r, c)
11      IF (nr, nc) NOT IN discovered
12        ADD (nr, nc) TO discovered
13        PUSH (grid[nr][nc], nr, nc) TO heap

← / → step · space play · Home restart

Where to practice Graph

Practice Graph problems All Graph problems Back to roadmap