TL;DR
Dijkstra with max instead of + as the path cost (minimax path) — O(n² log n) time, O(n²) space.
Approach 1 — Brute force (DFS over all simple paths)
Enumerate every simple path from (0, 0) to (n-1, n-1), tracking the max elevation seen; keep the smallest such max. Pruning branches that already meet or exceed the best answer helps, but not enough.
class Solution:
def swimInWater(self, grid: list[list[int]]) -> int:
n = len(grid)
best = [float("inf")]
def dfs(r: int, c: int, cur_max: int, visited: set) -> None:
cur_max = max(cur_max, grid[r][c])
if cur_max >= best[0]:
return
if r == n - 1 and c == n - 1:
best[0] = cur_max
return
visited.add((r, c))
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
dfs(nr, nc, cur_max, visited)
visited.remove((r, c))
dfs(0, 0, 0, set())
return best[0]
Complexity: the number of simple paths in a grid grows exponentially with n; at n = 50 (2500 cells) this never finishes.
Approach 2 — Binary search on time + BFS
The insight: feasibility is monotone in t — more water never hurts. So binary-search the smallest t for which a BFS restricted to cells with elevation ≤ t connects the corners.
from collections import deque
class Solution:
def swimInWater(self, grid: list[list[int]]) -> int:
n = len(grid)
def can_reach(t: int) -> bool:
if grid[0][0] > t:
return False
seen = {(0, 0)}
queue = deque([(0, 0)])
while queue:
r, c = queue.popleft()
if r == n - 1 and c == n - 1:
return True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if (0 <= nr < n and 0 <= nc < n
and (nr, nc) not in seen and grid[nr][nc] <= t):
seen.add((nr, nc))
queue.append((nr, nc))
return False
lo, hi = grid[0][0], n * n - 1
while lo < hi:
mid = (lo + hi) // 2
if can_reach(mid):
hi = mid
else:
lo = mid + 1
return lo
Walkthrough (grid = [[0,2],[1,3]]): range 0..3. mid = 1: BFS reaches (1,0) but both neighbors of the goal require ≥ 2 — fail, lo = 2. mid = 2: reach (0,1) and (1,0), but (1,1) has elevation 3 — fail, lo = 3 = hi. Answer 3.
Complexity: O(n² log(n²)) = O(n² log n) time (each check is a full BFS), O(n²) space.
Approach 3 — Dijkstra with max-cost paths (the intended solution)
The insight: Dijkstra’s algorithm (greedy shortest-path: always settle the frontier node with the smallest cost, via a min-heap) doesn’t actually require path cost to be a sum — it works for any cost that never decreases as a path grows. max(elevations on path) qualifies. Define the cost to reach a cell as the minimal water level needed; relax a neighbor with max(current_level, neighbor_elevation). The first pop of the goal is optimal, and unlike Approach 2 we solve it in a single pass with no repeated BFS.
import heapq
class Solution:
def swimInWater(self, grid: list[list[int]]) -> int:
n = len(grid)
heap = [(grid[0][0], 0, 0)] # (water level needed, row, col)
seen = {(0, 0)}
while heap:
t, r, c = heapq.heappop(heap)
if r == n - 1 and c == n - 1:
return t
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
seen.add((nr, nc))
level = max(t, grid[nr][nc])
heapq.heappush(heap, (level, nr, nc))
return -1 # unreachable; cannot happen on valid inputs
Walkthrough (grid = [[0,2],[1,3]]):
- Pop
(0, 0, 0). Push right: (max(0,2), 0, 1) = (2, 0, 1); push down: (1, 1, 0).
- Pop
(1, 1, 0) — cheapest frontier. Its unseen neighbor (1,1) pushes (max(1,3), 1, 1) = (3, 1, 1).
- Pop
(2, 0, 1) — its neighbor (1,1) is already seen.
- Pop
(3, 1, 1) — that’s the goal. Return 3.
Complexity: each cell enters the heap at most once → O(n² log n) time, O(n²) space.
Approach 4 — Union-find over cells sorted by elevation
The insight: simulate the water rising. At time t, “activate” the unique cell of elevation t and union it (union-find: near-O(1) merge/query of connected components) with any already-active neighbors. The answer is the first t at which the two corners share a component — a Kruskal-flavored view of the same minimax fact.
class Solution:
def swimInWater(self, grid: list[list[int]]) -> int:
n = len(grid)
parent = list(range(n * n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a: int, b: int) -> None:
parent[find(a)] = find(b)
pos = [0] * (n * n) # elevation -> flat cell index
for r in range(n):
for c in range(n):
pos[grid[r][c]] = r * n + c
for t in range(n * n):
idx = pos[t]
r, c = divmod(idx, n)
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] <= t:
union(idx, nr * n + nc)
if find(0) == find(n * n - 1):
return t
return n * n - 1
Complexity: O(n² α(n²)) ≈ O(n²) time after the O(n²) position table — asymptotically the best, though Dijkstra is the more commonly expected answer.
Common pitfalls
- Summing elevations like a normal shortest path — the cost of a path here is its maximum cell, and the start cell’s elevation counts too (
[[3,2],[0,1]] → 3, not 0 or 1).
- Marking
seen on pop instead of push in this Dijkstra variant is still correct but re-pushes cells many times; marking on push is safe here because the first push of a cell already carries its best-possible level only if popped in order — the standard lazy version (check on pop) is the safer general habit.
- Binary search bounds: the low end is
grid[0][0], not 0 — you can never start before your own cell is submerged.
- Forgetting movement is 4-directional; diagonal moves silently make examples “work” with wrong answers.
Pattern takeaway
When the objective is “minimize the worst edge/cell on a path” (minimax) rather than the total, you have three interchangeable tools: binary search on the threshold + BFS, Dijkstra with max replacing +, and union-find over edges/cells activated in ascending order (Kruskal’s view: the minimax path cost equals the bottleneck edge of the path in a minimum spanning tree). Dijkstra-with-max is the one to reach for first; the union-find formulation shines when many queries share one grid.