Swim in Rising Water
Swim in Rising Water: find the earliest water level at which a path exists from the top-left to bottom-right cell.
- n == grid.length
- n == grid[i].length
- 1 <= n <= 50
- 0 <= grid[i][j] < n²
- Each value grid[i][j] is unique.
Intuition
Swim in rising water asks for the earliest time you can travel from the top-left to the bottom-right of a grid, where you may enter a cell only once the water level reaches its elevation. Enumerating paths is exponential, and binary-searching the time while re-running a reachability check works but repeats the same traversal many times.
The reframing that solves it directly: a route's cost is not the sum of its cells but the maximum elevation along it. You wait for the highest cell on the path and everything else is already passable by then. So the answer is the path whose maximum elevation is smallest — a bottleneck or minimax path.
Dijkstra's algorithm normally accumulates costs by addition, but nothing in its correctness argument requires that. It needs only that extending a path never makes it cheaper, and max satisfies that just as addition does:
- Relax with max(currentCost, neighbourElevation) instead of currentCost + weight, and Dijkstra computes bottleneck paths unchanged.
The rest is familiar. A min-heap orders states by their bottleneck value, and the first time a cell is popped its value is final — any alternative route would have to pass through a state still in the heap, which already has a bottleneck at least as large.
So run Dijkstra from the top-left and return the moment the bottom-right cell is popped, not when it is first pushed. Being pushed only records a candidate; being popped is what proves it optimal.
A path objective that minimizes the maximum edge or vertex value is a bottleneck shortest-path problem. Dijkstra works by replacing additive relaxation with the operation that defines the path cost, here max.
Approach
Before reading on: price up what the direct approach costs here, then ask whether the weights force you past a plain breadth-first sweep. Aim for O(n^2 log n) time and O(n^2) space.
Redefine path cost as a bottleneck
A route's cost is the maximum elevation on it, not the sum — you wait for the highest cell and the rest are already covered. This single reframing is what turns an unclear search into a standard shortest-path problem.
Use max in the relaxation step
Moving to a neighbour gives cost max(currentCost, grid[nr][nc]). Dijkstra's proof only needs that extending never lowers the cost, which max satisfies, so the algorithm transfers with no other change.
Seed the heap with the start cell
Push (grid[0][0], 0, 0). The starting cell's own elevation is already part of the cost, since you must be able to enter it before the swim begins.
Pop the smallest bottleneck and relax
Take the minimum state from the heap, skip it if already finalised, then push each of the four neighbours with the max-combined cost. Lazy skipping is simpler than trying to decrease keys inside the heap.
Return when the destination is popped
Popping proves optimality; pushing does not. Any alternative route to that cell would pass through a state still in the heap with a bottleneck at least as large, so the popped value cannot be improved.
Compare with binary search plus BFS
Binary searching the time and running a reachability BFS per candidate also works, at O(n² log(n²)). Dijkstra reaches the same bound in one pass and avoids repeating the traversal — worth stating as the alternative you rejected.
Cost of the search
Each cell is pushed at most four times, once per neighbour, giving O(n² log n) time and O(n²) space for the heap and the finalised-cost grid.
Solution & live demo
Common pitfalls
Adding elevations
candidate = cost + grid[nr][nc]
candidate = max(cost, grid[nr][nc])
Waiting time is determined by the highest cell, not the sum of elevations.
Returning when the destination is pushed
if (nr, nc) == target:
return candidateif (row, col) == target:
return costA pushed destination may later receive a smaller bottleneck route.
Marking every discovered cell permanently
visited.add((nr, nc))
if candidate < best[nr][nc]:
best[nr][nc] = candidateA cell can be discovered first through a worse bottleneck.
Edge cases
The start is also the destination, so return its elevation.
Heap ordering can prefer a longer route with a lower maximum elevation.
Every route cost begins at that elevation and never decreases.