Appearance
4.21.4 — Swim in Rising Water
LeetCode 778 · Hard
The problem
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]] → 3You need to reach the cell with elevation 3, so you cannot arrive before time 3.
The pattern
The cost of a route is not the sum of its cells. You can swim through a route as soon as the water covers its highest cell, so:
\text{cost of a path} = \max(\text{elevations along it})
And the answer is the path whose maximum is smallest — a minimax path.
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.
This is the generalisation worth taking from the problem: Dijkstra works for any path cost that is monotonic — never improved by adding another step. Sum, maximum, and multiplying probabilities below 1 all qualify.
Solution 1 — Dijkstra with a maximum
python
import heapq
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
n = len(grid)
seen = [[False] * n for _ in range(n)]
heap = [(grid[0][0], 0, 0)] # (time needed so far, r, c)
while heap:
time, r, c = heapq.heappop(heap)
if seen[r][c]:
continue
seen[r][c] = True
if r == n - 1 and c == n - 1:
return time # first arrival is optimal
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 not seen[nr][nc]:
heapq.heappush(heap, (max(time, grid[nr][nc]), nr, nc))
return -1ts
function swimInWater(grid: number[][]): number {
const n = grid.length;
const seen = Array.from({ length: n }, () => new Array(n).fill(false));
const heap = new MinHeap<[number, number, number]>((e) => e[0]);
heap.push([grid[0][0], 0, 0]);
while (heap.size) {
const [time, r, c] = heap.pop()!;
if (seen[r][c]) continue;
seen[r][c] = true;
if (r === n - 1 && c === n - 1) return time;
for (const [nr, nc] of [[r+1,c],[r-1,c],[r,c+1],[r,c-1]] as [number,number][]) {
if (nr >= 0 && nr < n && nc >= 0 && nc < n && !seen[nr][nc]) {
heap.push([Math.max(time, grid[nr][nc]), nr, nc]);
}
}
}
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.
O(n^2 \log n) time, O(n^2) space.
Solution 2 — binary search plus flood fill
A different angle worth knowing, because it 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 loO(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.
Solution 3 — union-find
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.
Where this goes next
The minimax-path idea shows up more often than it looks:
- Path with Minimum Effort (LeetCode 1631) — minimise the largest difference between adjacent cells on the route. Same three solutions.
- Minimum Score of a Path — minimise, then take the smallest edge on the route.
- Bottleneck shortest path in networking — maximise the smallest bandwidth along a route, which is the mirror image.
The recognition cue: the path cost is a maximum or a minimum along the route rather than a sum. Dijkstra still applies; only the combine step changes.
What the interviewer will push on
"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.