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
- The 2D version of Trapping Rain Water. The water above a cell is bounded by the lowest surrounding "wall".
- Start from all border cells in a min-heap and expand inward.
- For each popped cell, the water trapped in a neighbour is
max(0, level - neighbour_height), wherelevelis the highest wall seen so far. - 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
levelinstead ofmax(level, height)for the neighbour: the wall only rises. - Forgetting the
m < 3 or n < 3case: 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.