⚡Flashcard Drill➔
NeetCode #635LC-407HardAdvanced Graphs
← Back to All Problems

#635 · #407 · Trapping Rain Water II(接雨水 II)

📌 Problem Statement & Constraints

Given an m x n matrix of heights, compute how much water it can trap after raining. Constraints: 1 <= m, n <= 200, 0 <= heightMap[i][j] <= 2 * 10^4.

💡 Core Algorithmic Approaches

  1. The 2D version of Trapping Rain Water. The water above a cell is bounded by the lowest surrounding "wall".
  2. Start from all border cells in a min-heap and expand inward.
  3. For each popped cell, the water trapped in a neighbour is max(0, level - neighbour_height), where level is the highest wall seen so far.
  4. Push the neighbour with max(level, neighbour_height) as the new level.

💻 Benchmark Python3 Implementation

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        import heapq
        m, n = len(heightMap), len(heightMap[0])
        if m < 3 or n < 3:
            return 0                       # no interior cell exists
        h = []
        seen = [[False] * n for _ in range(m)]
        # seed with the whole border
        for i in range(m):
            for j in range(n):
                if i == 0 or i == m - 1 or j == 0 or j == n - 1:
                    heapq.heappush(h, (heightMap[i][j], i, j))
                    seen[i][j] = True
        water = 0
        while h:
            level, r, c = heapq.heappop(h)   # the lowest wall so far
            for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc]:
                    seen[nr][nc] = True
                    water += max(0, level - heightMap[nr][nc])   # water above it
                    heapq.heappush(h, (max(level, heightMap[nr][nc]), nr, nc))
        return water

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n log(m * n)): each cell is pushed once.
💾 Space Complexity
O(m * n) for the heap and the visited grid.

⚠️ Interview Pitfalls & Follow-ups

  • Processing cells in row-major order: the walls must be processed by height, hence the heap.
  • Using level instead of max(level, height) for the neighbour: the wall only rises.
  • Forgetting the m < 3 or n < 3 case: no interior cell can hold water.
  • Trying a 2D DP of prefix maxima: it does not work because the boundary is a closed curve, not two sides.
⚡
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