The question “what’s the minimum t such that (0,0) and (n-1,n-1) are connected” is really: find the path from start to end that minimizes its maximum elevation cell, since you must wait for the water to rise to the highest point along whichever path you take. This “minimize the maximum edge/node weight along a path” shape is the minimax path problem, solvable by binary search + reachability check, a Dijkstra-flavored priority-first search, or (much like Kruskal’s MST) a union-find that adds cells in increasing elevation order.
Binary Search on Time + BFS Reachability
Time O(n² log(n²))Space O(n²)The set of times t for which (0,0) can reach (n-1,n-1) is monotonic: if it’s reachable at time t, it’s still reachable at any t' > t (submerging strictly more cells only helps). That monotonicity means we can binary search over t from 0 to n² - 1, and for each candidate run a BFS/DFS that only steps onto cells with elevation ≤ t.
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 visited = [[False] * n for _ in range(n)] visited[0][0] = True 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 not visited[nr][nc] and grid[nr][nc] <= t: visited[nr][nc] = True queue.append((nr, nc)) return False
lo, hi = 0, n * n - 1 while lo < hi: mid = (lo + hi) // 2 if can_reach(mid): hi = mid else: lo = mid + 1 return loEach BFS costs O(n²) (visiting every cell once), and binary search runs it O(log(n²)) = O(2 log n) times — O(n² log n) time overall, O(n²) space for the visited grid.
Dijkstra-Style Minimax Search with a Min-Heap
OptimalTime O(n² log n)Space O(n²)Instead of guessing t and re-running BFS, directly search for the minimax path in one pass: maintain a priority queue ordered by “the highest elevation seen so far on the path to this cell,” always expanding the cell whose current bottleneck is smallest — exactly like Dijkstra, but relaxation takes max(current_bottleneck, neighbor_elevation) instead of current_distance + edge_weight.
import heapq
class Solution: def swimInWater(self, grid: list[list[int]]) -> int: n = len(grid) visited = [[False] * n for _ in range(n)] pq = [(grid[0][0], 0, 0)] # (max elevation on path so far, r, c) visited[0][0] = True
while pq: t, r, c = heapq.heappop(pq) 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 not visited[nr][nc]: visited[nr][nc] = True heapq.heappush(pq, (max(t, grid[nr][nc]), nr, nc)) return -1 # unreachable, never happens per constraintsWatch the min-heap and the water badge act together: the queue always expands the cell with the lowest bottleneck, and the water level t rises only when a cell with a higher elevation must be crossed. Trace the file’s 2×2 example:
Elevations · start (0,0) · target (1,1)
Priority queue · min-heap (smallest bottleneck pops first)
At t = 0 the water submerges only cells with elevation ≤ 0 — just (0,0), the start. The priority queue holds its first entry: (0,0) with bottleneck 0. The bottleneck is the water level the path needs so far, and the queue always pops the smallest one first.
Why it’s correct: identical to Dijkstra’s correctness argument, with “distance” replaced by “path bottleneck” — since elevations are fixed (not decreasing), once a cell is popped with its minimum-possible bottleneck, no unexplored path can produce a smaller one (any such path’s bottleneck can only be ≥ the elevations already accounted for).
Complexity: every cell is pushed onto the heap at most once (guarded by visited), giving O(n²) heap operations at O(log n²) = O(log n) each — O(n² log n) time. Space is O(n²) for the visited grid and heap. This avoids the repeated-BFS overhead of the binary search approach while achieving the same asymptotic bound with a cleaner single pass.