DSA Tracker

Visualize

Swim in Rising Water

Dijkstra-style minimax: always pop the lowest unvisited elevation

time O(n^2 log n)space O(n^2)

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.

Details

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)?

Problem:Swim in Rising WaterHard

Pattern:Minimum Spanning Tree and Graph Greedy

Dijkstra-style minimax: always pop the lowest unvisited elevation

step 1 / 10

Badge = cell elevation

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

Every step in words

Show all 10 steps
  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).
  2. Push the start cell (0,0) — elevation 0 — onto a min-heap keyed by elevation. Always popping the SMALLEST elevation discovered so far is what keeps the running maximum, and therefore the final answer, as small as possible.
  3. Pop (0,0) at elevation 0, the smallest on the heap. Running maximum so far: MAX(previous, 0) = 0. Discover (1,0) at 6 and (0,1) at 4 — first time either is reachable, so both join the heap.
  4. Pop (0,1) at elevation 4, the smallest on the heap. Running maximum so far: MAX(previous, 4) = 4. Discover (1,1) at 1 and (0,2) at 2 — first time either is reachable, so both join the heap.
  5. Pop (1,1) at elevation 1, the smallest on the heap. Running maximum so far: MAX(previous, 1) = 4. Discover (2,1) at 7 and (1,2) at 8 — first time either is reachable, so both join the heap.
  6. Pop (0,2) at elevation 2, the smallest on the heap. Running maximum so far: MAX(previous, 2) = 4. Every neighbor was already discovered, so nothing new joins the heap.
  7. Pop (1,0) at elevation 6, the smallest on the heap. Running maximum so far: MAX(previous, 6) = 6. Discover (2,0) at 3 — first time either is reachable, so both join the heap.
  8. Pop (2,0) at elevation 3, the smallest on the heap. Running maximum so far: MAX(previous, 3) = 6. Every neighbor was already discovered, so nothing new joins the heap.
  9. Pop (2,1) at elevation 7, the smallest on the heap. Running maximum so far: MAX(previous, 7) = 7. Discover (2,2) at 5 — first time either is reachable, so both join the heap.
  10. Pop (2,2) at elevation 5 — the target. The running maximum is 7, and since every earlier pop was the cheapest elevation available at the time, no path could have reached here with a lower peak. RETURN 7.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Swim in Rising Water in the editorAll Graph problemsBack to roadmap