Swim in Rising Water: The Minimax Path Problem, Solved with Dijkstra
Solve Swim in Rising Water with a min-heap Dijkstra variant that minimizes the highest elevation on the path. Intuition, JavaScript, walkthrough, complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Most grid shortest-path problems ask you to minimize a sum — total steps, total cost. Swim in Rising Water quietly changes the rules: the cost of a path is the single highest elevation you cross, and you want the path whose highest elevation is as low as possible.
That one word — highest instead of total — breaks BFS and rewires the problem into something called a minimax path. The fix is a small, surgical edit to Dijkstra's algorithm, and once you see it you'll spot the same shape in a dozen "widest path" and "bottleneck" problems.
This walks through the exact min-heap solution the interactive visualizer steps through, cell by cell.
The problem
You're given an n x n grid where grid[i][j] is the elevation at cell (i, j). Water covers everything, and at time t the water depth everywhere is t. You may swim between two 4-directionally adjacent cells only if both of their elevations are at most t.
You start at the top-left cell (0, 0) and want to reach the bottom-right cell (n-1, n-1). Return the least time t at which that trip becomes possible.
Input: grid = [[0, 2],
[1, 3]]
Output: 3
The only ways to reach (1,1) pass through a cell of elevation 3.
Water must rise to t = 3 before that cell is swimmable, so the answer is 3.The key reframe hides in that example: reaching the target isn't about how far you swim, it's about the worst cell you're forced to cross. Water level t submerges every cell of elevation ≤ t, so the answer is the smallest t such that a path exists using only cells at or below t. That number equals the maximum elevation along the best possible route.
The brute force baseline
The most direct idea: try each candidate water level t = 0, 1, 2, … and, for each one, run a BFS/DFS that only walks through cells with elevation ≤ t. The first t from which the target is reachable is the answer.
function swimInWater(grid) {
const n = grid.length;
const maxElev = Math.max(...grid.flat());
for (let t = 0; t <= maxElev; t++) {
if (reachable(grid, t)) return t;
}
}
function reachable(grid, t) {
const n = grid.length;
if (grid[0][0] > t) return false;
const seen = Array.from({ length: n }, () => new Array(n).fill(false));
const stack = [[0, 0]];
seen[0][0] = true;
while (stack.length) {
const [r, c] = stack.pop();
if (r === n - 1 && c === n - 1) return true;
for (const [dr, dc] of [[0,1],[0,-1],[1,0],[-1,0]]) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n &&
!seen[nr][nc] && grid[nr][nc] <= t) {
seen[nr][nc] = true;
stack.push([nr, nc]);
}
}
}
return false;
}It works, but it re-explores the whole grid from scratch for every water level. With elevations up to n², that's O(n²) levels times an O(n²) flood fill — roughly O(n⁴). You can sharpen it to O(n² log n²) by binary searching on t instead of scanning linearly, since reachability is monotonic (if the target is reachable at t, it's reachable at every larger t). But there's a cleaner path that finds the answer in one pass.
The key insight: it's a minimax path, so use Dijkstra
Standard Dijkstra picks the frontier node with the smallest accumulated distance, where distance sums edge weights. The greedy argument — always expand the cheapest unfinished node — holds because a sum only grows as you extend a path.
Swim in Rising Water needs the same greedy expansion, but with the cost function swapped. The "cost" of arriving at a cell is the maximum elevation on the route that got you there, not the sum. That's still monotonic — extending a path can only keep or raise its maximum — so Dijkstra's greedy logic transfers directly:
Always expand the frontier cell with the lowest elevation first. The first time you pop a cell, you've reached it by the path with the smallest possible bottleneck.
Track a running maxTime — the highest elevation popped so far. Because you always pop the smallest available elevation, maxTime climbs as slowly as any valid route allows. The moment you pop the destination, maxTime is exactly the answer. This is the bottleneck shortest path, and a min-heap ordered by elevation is all it takes.
The optimal solution
Here's the min-heap Dijkstra the visualizer runs. The heap holds [elevation, row, col] entries; sorting by elevation before each pop keeps the lowest-elevation frontier cell at the front.
function swimInWater(grid) {
const n = grid.length;
const visited = Array.from({ length: n }, () => new Array(n).fill(false));
const minHeap = [[grid[0][0], 0, 0]]; // [time, r, c]
visited[0][0] = true;
let maxTime = 0;
while (minHeap.length > 0) {
minHeap.sort((a, b) => a[0] - b[0]);
const [t, r, c] = minHeap.shift();
maxTime = Math.max(maxTime, t);
if (r === n - 1 && c === n - 1) return maxTime;
const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
visited[nr][nc] = true;
minHeap.push([grid[nr][nc], nr, nc]);
}
}
}
return maxTime;
}Two details carry the correctness. First, maxTime = Math.max(maxTime, t) never decreases — it records the worst cell crossed so far, which is the water level required. Second, visited[nr][nc] = true is set the instant a neighbor is pushed, not when it's popped. Because the min-heap always surfaces the lowest elevation first, the first time a cell enters the heap is already via its best bottleneck, so re-adding it later could only offer a worse path. Marking on push avoids duplicate heap entries entirely.
(A production version would use a real binary heap for O(log k) pops; the sort-then-shift here mirrors the visualizer's step-authored code and reads more plainly.)
Walkthrough
Trace grid = [[0, 2], [1, 3]], where n = 2 and the target is (1, 1). Start: visited[0][0] = true, heap = [[0,0,0]], maxTime = 0.
Pop [t, r, c] | maxTime | Target? | Neighbors pushed | Heap after (sorted) |
|---|---|---|---|---|
[0, 0, 0] | 0 | no | (0,1) elev 2, (1,0) elev 1 | [1,1,0], [2,0,1] |
[1, 1, 0] | 1 | no (1,0) | (1,1) elev 3 | [2,0,1], [3,1,1] |
[2, 0, 1] | 2 | no (0,1) | none (all visited) | [3,1,1] |
[3, 1, 1] | 3 | yes | — | return 3 |
Watch the greedy order: from the start we could see elevations 2 and 1 on the frontier, and the heap popped the 1 first. That opened cell (1,0), which exposed the target at elevation 3. Even though (0,1) sat in the heap at elevation 2, the destination was only reachable through a cell of elevation 3, so maxTime climbed to 3 the instant we popped (1,1). No route bottlenecks lower than 3, and the min-heap proved it without trying every path.
Complexity
Let N = n² be the number of cells. Each cell is pushed and popped from the heap at most once.
| Metric | Value | Why |
|---|---|---|
| Time | O(N log N) = O(n² log n) | N pushes/pops, each O(log N) with a real heap |
| Space | O(N) = O(n²) | visited grid plus up to N cells on the heap |
The sort-based heap in the code above is O(N) per pop, making that exact snippet O(N²); swapping in a proper priority queue restores the O(N log N) bound stated here. Either way it's a single guided pass, versus the brute force's repeated floods.
Common mistakes
- Summing elevations like normal Dijkstra. The path cost is the
max, not the total. Accumulatingdist + weightgives the shortest-sum path, which is a different (usually wrong) route here. - Marking cells visited on pop instead of on push. Delay it and the same cell lands in the heap multiple times, bloating it and risking re-expansion. Mark the moment you push.
- Forgetting the start cell counts. Initialize
maxTimeand the heap withgrid[0][0]. On a grid like[[5,0],[0,0]]the answer is 5 purely because of the starting elevation. - Returning
tinstead ofmaxTime. The answer is the running maximum bottleneck, not the elevation of the last cell popped — though at the target they coincide only becausemaxTimewas updated first. - Using plain BFS. BFS finds the fewest-steps path, which ignores elevation entirely. The frontier must be ordered by elevation, and that requires a priority queue.
Where this pattern shows up next
The "order the frontier by a priority, expand greedily" engine behind this solution reappears across graph problems — sometimes minimizing a sum, sometimes a max, sometimes a step count:
- Word Ladder — a shortest-path over an implicit graph of words, where BFS layers replace the elevation heap.
- Reconstruct Itinerary — greedy edge ordering (lexicographic) drives a Hierholzer traversal instead of a min-heap.
- Breadth First Search (BFS) — the unweighted foundation; swap its queue for a priority queue and you get Dijkstra.
- Depth First Search (DFS) — the flood-fill core of the brute-force reachability check above.
To see the heap reorder and the bottleneck climb in real time, step through the Swim in Rising Water visualizer on the 2x2 grid, then on the 5x5 spiral.
FAQ
Why is Swim in Rising Water a Dijkstra problem and not BFS?
Because the answer depends on the elevation of cells, not the number of steps. BFS expands cells in order of distance from the start and finds the fewest-hops path, which tells you nothing about the highest elevation crossed. Dijkstra expands cells in order of a priority — here, elevation — so it always reaches the target through the route with the lowest possible bottleneck. The only change from a shortest-sum Dijkstra is that the cost of a path is max(elevations) rather than sum(edge weights).
What does "minimax path" mean here?
A minimax path minimizes the maximum edge (or node) weight along the route, rather than the total. In this problem the water level needed for a path equals the highest elevation on it, so finding the least water time is exactly finding the path whose maximum elevation is smallest — a minimax, or "bottleneck," shortest path. That maximum is monotonic under path extension, which is why Dijkstra's greedy expansion still produces the optimal answer.
What is the time complexity of the min-heap solution?
With a proper binary heap it's O(n² log n) for an n x n grid: there are n² cells, each pushed and popped once, and each heap operation costs O(log n²) = O(log n). Space is O(n²) for the visited matrix and the heap. The sort-then-shift version shown in the code is O(n⁴) because sorting every pop is O(n²); it's written that way for clarity and matches the visualizer's step-by-step trace.
Can I solve it with binary search instead?
Yes. Because reachability is monotonic in the water level — if you can cross at time t, you can cross at any t' > t — you can binary search t over [0, n²−1] and run a BFS/DFS reachability check at each candidate. That's O(n² log n²) time, the same asymptotic ballpark as heap Dijkstra. Dijkstra wins on elegance: it finds the exact bottleneck in one pass without guessing a threshold, whereas binary search probes a range of candidate levels.
Why mark a cell visited when I push it, not when I pop it?
Because the min-heap guarantees the first time a cell is offered to the frontier is already via its lowest-bottleneck route. Any later push of the same cell would come from a path with an equal-or-higher maximum elevation, so it can't improve the answer. Marking on push keeps each cell out of the heap after its first appearance, preventing duplicate entries and redundant expansion. Marking on pop instead lets copies pile up, which still returns the right answer but wastes time and memory.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.