Swim in Rising Water
You are given an n x n grid where gridi[j] is the elevation of the square (i, j). Rain starts to fall, and at time t, the water level is t everywhere. You can swim from one square to an adjacent one only if both squares have elevation at most the current water level. Starting at (0, 0), return the least time until you can reach (n - 1, n - 1). This is another minimax Dijkstra : the cost of a route is the highest single elevation it passes through, and relaxing a neighbor takes the larger of the current cost and that neighbor’s own elevation.
Constraints
- n == grid.length == gridi.length
- 1 ≤ n ≤ 50
- 0 ≤ gridi[j] < n^2
Example
grid = [[0,2],[1,3]]3Explanation At time 3, elevations 0, 2, 1 and 3 are all swimmable, and (0,0) can reach (1,1) through either neighbor.
In plain terms
- Minimax path
- A path chosen to minimize its single worst step — here, the highest elevation crossed — rather than the total distance travelled.
Pop the least-cost cell, relax with max(cost, elevation)
Start at (0,0), elevation 0 — the water level needed here is just its own height.
What happens in this step
cost[0,0] = grid[0][0] = 0 every other cell = ∞ The source cell's cost starts at its own elevation, not 0 — you always need at least enough water to cover the square you're standing on.
Steps to visualize
- Set the cost of the top-left cell to its own elevation and every other cell to infinity.
- Repeatedly pop the unfinalized cell with the smallest cost.
- Relax each neighbor: its candidate cost is the larger of the current cell’s cost and the neighbor’s own elevation.
- Once the bottom-right cell is popped, its cost is the minimum time needed to swim there.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Start at (0,0), elevation 0 — the water level needed here is just its own height.
What happens in this step
cost[0,0] = grid[0][0] = 0 every other cell = ∞ The source cell's cost starts at its own elevation, not 0 — you always need at least enough water to cover the square you're standing on.
Solution
function swimInWater(grid) {
const n = grid.length;
const cost = Array.from({ length: n }, () => new Array(n).fill(Infinity));
cost[0][0] = grid[0][0];
const visited = Array.from({ length: n }, () => new Array(n).fill(false));
const directions = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
];
while (true) {
let cr = -1;
let cc = -1;
let best = Infinity;
for (let r = 0; r < n; r++) {
for (let c = 0; c < n; c++) {
if (!visited[r][c] && cost[r][c] < best) {
best = cost[r][c];
cr = r;
cc = c;
}
}
}
if (cr === -1) break;
if (cr === n - 1 && cc === n - 1) break; // destination popped, done
visited[cr][cc] = true;
for (const [dr, dc] of directions) {
const nr = cr + dr;
const nc = cc + dc;
if (nr < 0 || nr >= n || nc < 0 || nc >= n || visited[nr][nc]) continue;
const candidate = Math.max(cost[cr][cc], grid[nr][nc]); // max, not sum
if (candidate < cost[nr][nc]) {
cost[nr][nc] = candidate;
}
}
}
return cost[n - 1][n - 1];
}- Time
- O(n^4)
- Space
- O(n^2)
Test cases
| Input | Expected | Covers |
|---|---|---|
grid = [[0,2],[1,3]] | 3 | example from the docstring |
grid = [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]] | 16 | a larger spiral grid where the safe route still passes through a high value |
grid = [[0]] | 0 | start and destination are the same single cell |
grid = [[0,1,2],[3,4,5],[6,7,8]] | 8 | the destination's own elevation sets a hard lower bound on the answer |
grid = [[0,1],[3,2]] | 2 | the destination itself becomes reachable before its higher neighbor is ever needed |
grid = [[0,1,6],[2,3,7],[8,4,5]] | 5 | the cheapest route matches the theoretical lower bound set by the destination elevation |
grid = [[0,4,8],[1,5,7],[2,3,6]] | 6 | a different permutation where the safest route again matches the lower bound |