Why Underwater Does Not Mean Reachable
In our 3 × 3 grid, (2, 2) sits at elevation 3. At t = 3, water covers (0, 0), (1, 0), (2, 0), and (2, 2) — yet (2, 2) is an isolated puddle! Every route out of the left column hits the ridge 6, 5, or 4. Only when t = 4 submerges (2, 1) does a continuous 4-way corridor open from start to finish.
Replacing + With max Inside Dijkstra
Standard Dijkstra relaxes edges using candidate = cost + weight. Here, water depth does not accumulate; crossing a cell only requires the water to be at least as high as that cell:
candidate = max(level, grid[nr][nc])Because max(level, grid[nr][nc]) >= level is monotonically non-decreasing, no waiting heap entry with water level ≥ 4 can ever later discover a path with water level < 4.
Clean Python Solution
from heapq import heappop, heappush
def swim_in_water(grid: list[list[int]]) -> int:
n = len(grid)
best = [[float("inf")] * n for _ in grid]
best[0][0] = grid[0][0]
heap = [(grid[0][0], 0, 0)]
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while heap:
level, r, c = heappop(heap)
if level != best[r][c]:
continue
if (r, c) == (n - 1, n - 1):
return level
for dr, dc in directions:
nr, nc = r + dr, c + dc
if not (0 <= nr < n and 0 <= nc < n):
continue
candidate = max(level, grid[nr][nc])
if candidate < best[nr][nc]:
best[nr][nc] = candidate
heappush(heap, (candidate, nr, nc))
raise ValueError("Grid must be non-empty")Complexity & Related Alternatives
- Time Complexity:
O(n² log n)— each of then²cells is settled once and pushes up to 4 neighbors;log(n²) = 2 log n. - Space Complexity:
O(n²)forbestand the min-heap. - Alternatives: Binary Search on
t+ BFS (O(n² log n)), or sorting cells by elevation + Union-Find (O(n² log n)).