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 is not enough.
def swimInWater(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
Feasibility is monotone in t: raising the water level never disconnects a route that already worked. So binary-search the smallest t for which a BFS restricted to cells with elevation ≤ t connects the corners.
from collections import deque
def swimInWater(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)
Dijkstra (always settle the frontier node with the smallest cost, via a min-heap) does not require the path cost to be a sum. It works for any cost that never decreases as a path grows, and max(elevations on path) qualifies. Define the cost to reach a cell as the minimal water level needed, and relax a neighbor with max(current_level, neighbor_elevation). The first pop of the goal is optimal, and unlike Approach 2 this is a single pass with no repeated BFS.
import heapq
def swimInWater(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]]). The grid as a graph, each cell labeled with its elevation:
graph LR
A["(0,0) = 0"] --- B["(0,1) = 2"]
A --- C["(1,0) = 1"]
B --- D["(1,1) = 3"]
C --- D
The goal (1,1) has elevation 3, so every path into it crosses a cell of value 3; the minimax cost is 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
Simulate the water rising. At time t, activate the unique cell of elevation t and union it (union-find: near-O(1) merge and 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-style view of the same minimax fact.
def swimInWater(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 a cell
seen on push (as in Approach 3) is correct here: cells pop in nondecreasing level order, so the first time a cell is reached it already carries the smallest level needed. The general-purpose habit is to mark on pop and skip stale heap entries, which also works but pushes each cell several times.
- 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. Allowing diagonal moves silently produces wrong answers that still look plausible on the examples.
Pattern takeaway
When the objective is to minimize the worst edge or cell on a path (minimax) instead of the total, three interchangeable tools apply: binary search on the threshold plus BFS, Dijkstra with max replacing +, and union-find over edges or cells activated in ascending order (Kruskal’s view: the minimax path cost equals the bottleneck edge of the path in a minimum spanning tree). Reach for Dijkstra-with-max first; the union-find formulation is best when many queries share one grid.