⚡Flashcard Drill➔
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

  1. This is a Dijkstra variant that minimises the maximum along the path rather than the sum.
  2. The heap key is the maximum elevation encountered so far, and neighbours are pushed with max(current, neighbour).
  3. The first time the destination is popped, that maximum is the answer.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Advanced Graphs Problems