Swim in Rising Water
Find the earliest time you can swim from the top-left to the bottom-right of an elevation grid with Dijkstra, where a path costs its highest cell.
Problem Understanding
Swim in Rising Water: grid[r][c] is the elevation of each cell in an n × n grid. At time t the water level is t, and you can swim between adjacent cells whose elevations are both at most t, instantly. Return the least time you can reach (n-1, n-1) starting from (0, 0).
Example: [[0,2],[1,3]] returns 3: you cannot leave the corner before t = 3, because the target itself is 3.
The Intuition: A Path Costs Its Highest Cell
Swimming is instant, so only the water level matters. A route becomes usable once the water covers its highest cell. The question is therefore: which path from corner to corner has the smallest maximum elevation?
- Treat it as shortest path where a path's cost is
max, not+. - Run Dijkstra with a min-heap of
(time, cell): pop the cell reachable at the lowest time, then push its neighbours withmax(time, elevation). - The first time the bottom-right cell is popped, its time is the answer.
It is the same loop as Network Delay Time, on a grid instead of a graph and with max in place of +.
Interactive Walkthrough
Each cell shows its elevation; the number under it is the earliest time found to reach it. Settled cells are tinted and the best path turns green at the end. Try Spiral to see the search hug the low edge and skip the high centre.
Dry Run Table
Input: grid = [[0,2],[1,3]]
| Pop (time, cell) | Pushed | Heap after |
|---|---|---|
| (0, (0,0)) | (1,0) at max(0,1) = 1, (0,1) at max(0,2) = 2 | (1, (1,0)), (2, (0,1)) |
| (1, (1,0)) | (1,1) at max(1,3) = 3 | (2, (0,1)), (3, (1,1)) |
| (2, (0,1)) | none, (1,1) already seen | (3, (1,1)) |
| (3, (1,1)) | target reached |
Answer: 3.
The Solution Template
Min-heap Dijkstra keyed on the highest elevation so far. JavaScript and TypeScript include a small binary heap. C uses the O(n⁴) array scan instead of a heap, which is fine for n ≤ 50.
Swim in Rising Water Code
1var swimInWater = function(grid) {2 const n = grid.length, seen = new Set(['0,0']);3 const heap = [[grid[0][0], 0, 0]];4 while (heap.length) {5 const [t, r, c] = pop(heap);6 if (r === n - 1 && c === n - 1) return t;7 for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {8 if (nr < 0 || nr >= n || nc < 0 || nc >= n || seen.has(nr + ',' + nc)) continue;9 seen.add(nr + ',' + nc);10 push(heap, [Math.max(t, grid[nr][nc]), nr, nc]);11 }12 }13};1415// Minimal binary min-heap on [time, row, col].16function push(heap, item) {17 heap.push(item);18 let i = heap.length - 1;19 while (i > 0) {20 const p = (i - 1) >> 1;21 if (heap[p][0] <= heap[i][0]) break;22 [heap[p], heap[i]] = [heap[i], heap[p]];23 i = p;24 }25}2627function pop(heap) {28 const top = heap[0], last = heap.pop();29 if (heap.length) {30 heap[0] = last;31 let i = 0;32 while (true) {33 let m = i;34 const l = 2 * i + 1, r = l + 1;35 if (l < heap.length && heap[l][0] < heap[m][0]) m = l;36 if (r < heap.length && heap[r][0] < heap[m][0]) m = r;37 if (m === i) break;38 [heap[m], heap[i]] = [heap[i], heap[m]];39 i = m;40 }41 }42 return top;43}
Edge Cases & Common Mistakes
- High start cell: you cannot move before
t = grid[0][0]; seeding the heap with that value handles it. - High target cell: the answer is at least
grid[n-1][n-1], as in[[0,2],[1,3]]. - Adding elevations: the cost is the maximum on the path, not the sum.
- Marking cells seen on pop instead of push: still correct, but the same cell can then sit in the heap several times.
- BFS without a heap: fewest steps is not lowest water level; a long low route can beat a short high one.
Summary
A path is usable once the water covers its highest cell, so run Dijkstra with a min-heap keyed on max(time, elevation). The first pop of the bottom-right cell gives the answer. O(n² log n) time and O(n²) space.
More practice: DSA interview questions with answers · patterns cheat sheet