NeetCode #633LC-778HardAdvanced GraphsNC 150NC 250
← Back to All Problems#633 · #778 · Swim in Rising Water(水位上升的泳池中游泳)
📌 Problem Statement & Constraints
You are given an
n x n grid where grid[i][j] is the elevation. Rain starts falling at time t, and you can swim to adjacent cells only when both elevations are at most t. Return the least t to swim from the top-left to the bottom-right. Constraints: 1 <= n <= 50, 0 <= grid[i][j] < n^2, all elevations are distinct.💡 Core Algorithmic Approaches
- This is a Dijkstra variant that minimises the maximum along the path rather than the sum.
- The heap key is the maximum elevation encountered so far, and neighbours are pushed with
max(current, neighbour). - The first time the destination is popped, that maximum is the answer.
- The same template solves Path With Minimum Effort and Path With Maximum Minimum Value.
💻 Benchmark Python3 Implementation
class Solution:
def swimInWater(self, grid: List[List[int]]) -> int:
import heapq
n = len(grid)
h = [(grid[0][0], 0, 0)] # (max elevation so far, r, c)
seen = {(0, 0)}
while h:
t, r, c = heapq.heappop(h)
if r == n - 1 and c == n - 1:
return t # the bottleneck is the answer
for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in seen:
seen.add((nr, nc))
heapq.heappush(h, (max(t, grid[nr][nc]), nr, nc))
return -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2 log n): each cell is pushed once.
💾 Space Complexity
O(n^2) for the heap and the visited set.
⚠️ Interview Pitfalls & Follow-ups
- Summing elevations instead of taking the maximum: the objective is the bottleneck, not the total.
- Using binary search plus BFS: also correct and O(n^2 log V), but the Dijkstra variant is a single pass.
- Marking visited when popping instead of when pushing: workable, but the first pop is optimal here, so pushing-time marking is safe.
- Forgetting that the start elevation counts: the initial key is
grid[0][0].
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.