Each cell of an n × n grid has an elevation. At time t the water level is t, and you may swim between adjacent cells if both are at or below the water level. Return the earliest time you can reach the bottom-right corner from the top-left.
grid = [[0,2],[1,3]] → 3
In plain English, you are placed on a 2D grid of terrain where each cell has a height. At time t=0, the water level is 0, and it rises by 1 unit every unit of time. You can only swim to a neighboring cell if the water level has risen enough to completely cover both your current cell and the neighboring cell. What is the absolute earliest time you can reach the bottom-right corner?
You need to reach the cell with elevation 3, so you cannot arrive before time 3.
Imagine you are driving an off-road vehicle across a desert from the top-left to the bottom-right, but there are massive sand dunes everywhere. Your vehicle has a "max dune height" it can climb. If you pick a path that has twenty small 5-foot dunes, your vehicle only needs a rating of 5. But if you pick a shortcut path that is mostly flat but has one massive 50-foot dune, you need a rating of 50 to survive that route! You want to buy the cheapest vehicle possible (lowest rating). So you don't care about the sum of the dunes on a path; you only care about the single highest dune on that path. You want the path where the highest dune is as small as possible.
That is still Dijkstra. Dijkstra never actually requires addition; it requires that extending a path cannot make it cheaper. Replacing "sum so far plus edge weight" with "maximum so far versus cell elevation" keeps that property, because a maximum never decreases.
The general idea to take from this problem: Dijkstra works for any path cost that is monotonic, meaning it never improves by adding another step. Sum, maximum, and multiplying probabilities below 1 all qualify.
import heapqclass Solution: def swimInWater(self, grid: List[List[int]]) -> int: n = len(grid) seen = [[False] * n for _ in range(n)] # (1) heap = [(grid[0][0], 0, 0)] # (2) (time needed so far, r, c) while heap: time, r, c = heapq.heappop(heap) # (3) if seen[r][c]: # (4) continue seen[r][c] = True # (5) if r == n - 1 and c == n - 1: # (6) return time # first arrival is optimal for nr, nc in ((r+1,c), (r-1,c), (r,c+1), (r,c-1)): # (7) if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]: heapq.heappush(heap, (max(time, grid[nr][nc]), nr, nc)) # (8) return -1
ts
function swimInWater(grid: number[][]): number { const n = grid.length; const seen = Array.from({ length: n }, () => new Array(n).fill(false)); // (1) const heap = new MinHeap<[number, number, number]>((e) => e[0]); heap.push([grid[0][0], 0, 0]); // (2) while (heap.size) { const [time, r, c] = heap.pop()!; // (3) if (seen[r][c]) continue; // (4) seen[r][c] = true; // (5) if (r === n - 1 && c === n - 1) return time; // (6) for (const [nr, nc] of [[r+1,c],[r-1,c],[r,c+1],[r,c-1]] as [number,number][]) { // (7) if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc]) { heap.push([Math.max(time, grid[nr][nc]), nr, nc]); // (8) } } } return -1;}
max(time, grid[nr][nc]) replaces the usual cost + weight. That single substitution turns Dijkstra from a shortest-sum algorithm into a smallest-maximum one.
The start cost is grid[0][0], not 0 — you must wait for the water to cover the starting cell before you can move at all.
Returning on first arrival is the same guarantee as ordinary Dijkstra: the first pop of a node is its optimal value.
(1) seen[r][c] marks cells whose best time is final.
(2) A heap of (time, r, c), smallest time first. The "time" for a cell is the earliest moment you could be standing there, which is the highest cell on the best path so far. You cannot even stand on the starting cell until the water reaches its height, so we start with grid[0][0].
(3) Take the cell you can reach soonest.
(4) Already final? Skip this out-of-date entry.
(5) Mark it final. As in Dijkstra's algorithm in 4.21.3, the first time a cell leaves the heap, its time cannot be beaten.
(6) Reached the bottom-right corner, so this time is the answer.
(7) Look at the four neighbours.
(8) The time to reach a neighbour through this cell is the larger of the time so far and the neighbour's own height. This is the one change from ordinary Dijkstra: a path's cost is not the sum of its steps but the highest point along it. max replaces +. Dijkstra still works, because a path's highest point can never go down as the path gets longer, just as a sum of non-negative times can never go down.
A different angle, and one that is often easier to reach under pressure.
Ask: at time t, can I get from corner to corner? That is a plain flood fill over the cells with elevation ≤ t.
And the answers are monotonic — if you can swim at time t, you can swim at any later time, because the water only rises. So binary search the time (4.11.3).
python
def swimInWater(self, grid): n = len(grid) def reachable(t) -> bool: if grid[0][0] > t: return False seen = {(0, 0)} stack = [(0, 0)] while stack: r, c = stack.pop() if (r, c) == (n-1, n-1): return True for nr, nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)): if 0 <= nr < n and 0 <= nc < n and (nr,nc) not in seen and grid[nr][nc] <= t: seen.add((nr, nc)) stack.append((nr, nc)) return False lo, hi = grid[0][0], n * n - 1 while lo < hi: mid = (lo + hi) // 2 if reachable(mid): hi = mid else: lo = mid + 1 return lo
O(n^2 \log(n^2)), which is O(n^2 \log n) — the same as Dijkstra. The elevations are a permutation of 0 … n²−1, which is what bounds the search range.
Say both. Binary search plus a reachability check is a pattern that solves many "smallest threshold that makes something possible" problems, and recognising that this is one of them is worth as much as the Dijkstra version.
Sort the cells by elevation and add them one at a time, unioning each with its already-added neighbours. The answer is the elevation at which the two corners first become connected.
O(n^2 \log n) for the sort, then effectively linear. It is the neatest of the three and the least obvious.
It is also the same shape as Kruskal's algorithm in 4.21.2 — process in increasing weight order and union — which is a nice connection to draw.
"Why does Dijkstra still work when the cost is a maximum?" Because a maximum never decreases as the path grows, so extending a path cannot improve it — which is the only property Dijkstra needs.
"Why is the start cost grid[0][0]?" You cannot move until the water covers the starting cell.
"Can you do it without a heap?" Binary search the time plus a flood fill, or union-find by increasing elevation.
"Which of the three would you write?" Any; say the complexities are equal and that binary search is the easiest to get right under pressure.
"What if you had to minimise the sum instead?" Ordinary Dijkstra, cost + grid[nr][nc].
One thing to volunteer: state the cost model explicitly before coding. "The cost of a path is the maximum cell on it, not the sum." Everything downstream depends on that sentence, and it is where wrong solutions come from.
Next:4.21.5 Alien Dictionary — where the difficulty is building the graph, not searching it.