Swim in rising water
An n × n grid holds distinct elevations from 0 to n² − 1. At time
t the water is at depth t everywhere, and you can swim between adjacent cells (up, down,
left, right) only if both are at elevation at most t. Swimming itself takes no time. Starting at the
top-left cell, return the least time at which you can reach the bottom-right cell.
Examples
| Input | Output | Why |
|---|---|---|
grid = [[0,2],[1,3]] | 3 | The target itself is at elevation 3, so nothing earlier can work. |
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 | The spiral along the edge and into row 2 never goes above 16. |
grid = [[0]] | 0 | Already there. |
Constraints
- 1 ≤ n ≤ 50
- The elevations are a permutation of 0 … n² − 1
Hints
Hint 1
The time a route becomes usable is the highest elevation on it, including the start and the end.
Hint 2
So you want the route whose highest cell is lowest: a minimax path, which Dijkstra handles with max in place of +.
Hint 3
Start with the cost of the start cell itself, and relax a neighbour with max(cost so far, its elevation).
Where people lose marks
- Forgetting that the start cell's own elevation counts: the answer is at least grid[0][0].
- Counting the number of steps: swimming takes no time.
- Breadth-first search by steps, which finds the shortest route, not the lowest one.
Dry run on [[0,8,7],[1,6,5],[2,3,4]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5settled cells and their time(0,0):00
Settle (0, 0) at time 0: nothing left in the heap is lower. Neighbours updated: (1,0)→1, (0,1)→8.
-
Step 2 / 5settled cells and their time(0,0):00(1,0):11
Settle (1, 0) at time 1: nothing left in the heap is lower. Neighbours updated: (2,0)→2, (1,1)→6.
-
Step 3 / 5settled cells and their time(0,0):00(1,0):11(2,0):22
Settle (2, 0) at time 2: nothing left in the heap is lower. Neighbours updated: (2,1)→3.
-
Step 4 / 5settled cells and their time(0,0):00(1,0):11(2,0):22(2,1):33
Settle (2, 1) at time 3: nothing left in the heap is lower. Neighbours updated: (2,2)→4.
-
Step 5 / 5settled cells and their time(0,0):00(1,0):11(2,0):22(2,1):33(2,2):44
Settle (2, 2) at time 4: nothing left in the heap is lower. It is the target: the answer is 4.
How to think about it
A route can be swum at time t exactly when every cell on it has elevation at most t. So the earliest time for a route is the highest elevation on it, and the answer is the smallest such maximum over all routes.
Extending a route never lowers its maximum, so Dijkstra applies with the combine step
max(cost[u], elevation[v]), starting from the start cell's own elevation. The first time the bottom-right
cell is popped from the heap, its cost is the answer.
Two other correct solutions: binary search on t with a reachability search, or add cells to a union-find in increasing order of elevation until the two corners are joined.
Complexity. Time O(n² log n) · Space O(n²)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
import heapq
def swim_in_water(grid):
n = len(grid)
best = [[float('inf')] * n for _ in range(n)]
best[0][0] = grid[0][0] # the start cell's own height counts
heap = [(grid[0][0], 0, 0)]
while heap:
t, r, c = heapq.heappop(heap)
if t > best[r][c]:
continue # stale entry
if r == n - 1 and c == n - 1:
return t
for a, b in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= a < n and 0 <= b < n:
nt = max(t, grid[a][b]) # the highest cell on the route so far
if nt < best[a][b]:
best[a][b] = nt
heapq.heappush(heap, (nt, a, b))
return -1#include <algorithm>
#include <array>
#include <climits>
#include <functional>
#include <queue>
#include <vector>
int solve(const std::vector<std::vector<int>>& grid) {
const int n = grid.size();
std::vector<std::vector<int>> best(n, std::vector<int>(n, INT_MAX));
best[0][0] = grid[0][0]; // the start cell counts
using Entry = std::array<int, 3>;
std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap;
heap.push({grid[0][0], 0, 0});
const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
while (!heap.empty()) {
auto [t, r, c] = heap.top();
heap.pop();
if (t > best[r][c]) continue; // stale entry
if (r == n - 1 && c == n - 1) return t;
for (int d = 0; d < 4; ++d) {
int a = r + dr[d], b = c + dc[d];
if (a < 0 || b < 0 || a >= n || b >= n) continue;
int nt = std::max(t, grid[a][b]); // highest cell on the route
if (nt < best[a][b]) { best[a][b] = nt; heap.push({nt, a, b}); }
}
}
return -1;
}import java.util.*;
class Solution {
public int swimInWater(int[][] grid) {
int n = grid.length;
int[][] best = new int[n][n];
for (int[] row : best) Arrays.fill(row, Integer.MAX_VALUE);
best[0][0] = grid[0][0]; // the start cell counts
PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> Integer.compare(x[0], y[0]));
heap.add(new int[]{grid[0][0], 0, 0});
int[] dr = {1, -1, 0, 0}, dc = {0, 0, 1, -1};
while (!heap.isEmpty()) {
int[] e = heap.poll();
int t = e[0], r = e[1], c = e[2];
if (t > best[r][c]) continue; // stale entry
if (r == n - 1 && c == n - 1) return t;
for (int d = 0; d < 4; d++) {
int a = r + dr[d], b = c + dc[d];
if (a < 0 || b < 0 || a >= n || b >= n) continue;
int nt = Math.max(t, grid[a][b]); // highest cell on the route
if (nt < best[a][b]) { best[a][b] = nt; heap.add(new int[]{nt, a, b}); }
}
}
return -1;
}
}function swimInWater(grid) {
const n = grid.length;
const best = Array.from({ length: n }, () => new Array(n).fill(Infinity));
best[0][0] = grid[0][0]; // the start cell counts
const heap = [[grid[0][0], 0, 0]];
const push = e => { heap.push(e); let i = heap.length - 1; while (i > 0) { const p = (i - 1) >> 1; if (heap[p][0] <= heap[i][0]) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } };
const pop = () => { const top = heap[0], last = heap.pop(); if (heap.length) { heap[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let m = i; if (l < heap.length && heap[l][0] < heap[m][0]) m = l; if (r < heap.length && heap[r][0] < heap[m][0]) m = r; if (m === i) break; [heap[m], heap[i]] = [heap[i], heap[m]]; i = m; } } return top; };
while (heap.length) {
const [t, r, c] = pop();
if (t > best[r][c]) continue; // stale entry
if (r === n - 1 && c === n - 1) return t;
for (const [a, b] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
if (a < 0 || b < 0 || a >= n || b >= n) continue;
const nt = Math.max(t, grid[a][b]); // highest cell on the route
if (nt < best[a][b]) { best[a][b] = nt; push([nt, a, b]); }
}
}
return -1;
}use std::cmp::Reverse;
use std::collections::BinaryHeap;
fn solve<const N: usize>(grid: &[[i64; N]]) -> i64 {
let n = grid.len();
let mut best = vec![[i64::MAX; N]; n];
best[0][0] = grid[0][0]; // the start cell counts
let mut heap = BinaryHeap::from([Reverse((grid[0][0], 0usize, 0usize))]);
while let Some(Reverse((t, r, c))) = heap.pop() {
if t > best[r][c] {
continue; // stale entry
}
if r == n - 1 && c == N - 1 {
return t;
}
let around = [(r + 1, c), (r.wrapping_sub(1), c), (r, c + 1), (r, c.wrapping_sub(1))];
for (a, b) in around {
if a >= n || b >= N {
continue;
}
let nt = t.max(grid[a][b]); // highest cell on the route
if nt < best[a][b] {
best[a][b] = nt;
heap.push(Reverse((nt, a, b)));
}
}
}
-1
}import qualified Data.Map.Strict as M
import qualified Data.Set as S
solve :: [[Int]] -> Int
solve grid = go (S.singleton (g M.! (0, 0), (0, 0))) (M.singleton (0, 0) (g M.! (0, 0)))
where
n = length grid
g = M.fromList [((r, c), x) | (r, row) <- zip [0 ..] grid, (c, x) <- zip [0 ..] row]
-- the set of (time, cell) is the heap; the start cell's own height counts
go heap best = case S.minView heap of
Nothing -> -1
Just ((t, p@(r, c)), rest)
| t > M.findWithDefault maxBound p best -> go rest best -- stale entry
| p == (n - 1, n - 1) -> t
| otherwise ->
let moves = [ (nt, q) | q <- [(r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)], M.member q g
, let nt = max t (g M.! q) -- highest cell so far
, nt < M.findWithDefault maxBound q best ]
in go (foldr S.insert rest moves) (foldr (\(nt, q) -> M.insert q nt) best moves)Variants to try
- Return the route.
- Elevations are not distinct and the grid is rectangular: the same algorithm works unchanged.
- Solve it with union-find, adding cells in order of elevation.
Next problems
The path with the least effort
Cross a grid of heights from corner to corner so that the steepest single step is as gentle as possible. Dijkstra, with max in place of +.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem →Write a solution and run it against the real test table.
Keep going
The path with the least effort
Cross a grid of heights from corner to corner so that the steepest single step is as gentle as possible. Dijkstra, with max in place of +.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → Easy12 minDoes an undirected graph contain a cycle?
Return true if the graph has a cycle: a search that meets a visited node by any edge but the one it came along has found one.
Open the problem → GraphsThe pattern behind it
Grids, networks and dependencies are all graphs. Breadth-first search finds shortest paths, depth-first search and union-find find what is connected, Dijkstra handles weighted edges, and a queue of nodes with no remaining prerequisites gives an order.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.