📘 Problem Statement
Given an m x n matrix representing the elevation map, where each element represents the height of a particular cell, your task is to compute how much rainwater can be trapped after it rains.
Input:
- A 2D matrix of integers
heightMap where heightMap[i][j] represents the height of the terrain at that point.
Output:
- The total amount of water that can be trapped after it rains.
🧠 Key Insight
This problem is a variation of the 1D "Trapping Rain Water" problem, extended to two dimensions. The idea is to treat the matrix as a terrain map where the goal is to calculate how much water can accumulate between the cells after raining.
We can solve this problem using a Priority Queue (Min-Heap) combined with a BFS/DFS-like approach. Here's the reasoning behind the approach:
- Initial Boundary Processing: Water cannot be trapped at the boundary of the elevation map because it would flow out. Therefore, we process the boundary cells first.
- Min-Heap for Efficient Processing: We use a min-heap to always expand from the lowest elevation. This helps us simulate how water would flow in the terrain.
- Flood Fill: As we process each cell, we "flood" the neighboring cells with water if they are lower than the current boundary, updating the total water trapped.
💡 Approach
- Initialize the Min-Heap: Insert all boundary cells (the cells along the edges of the matrix) into a min-heap. These are the starting points where water could potentially flow out.
- Flood Fill with Min-Heap: Pop the smallest element from the heap (which represents the current boundary), and check its neighboring cells. If a neighboring cell is lower, water can be trapped in it, so we add the difference in height to the total trapped water and push the neighbor into the heap with the updated height (to reflect the new boundary).
- Repeat Until All Cells Are Processed: Continue the process until all cells have been processed.
🐍 Python Code
python
import heapq
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
if not heightMap or not heightMap[0]:
return 0
m, n = len(heightMap), len(heightMap[0])
visited = [[False] * n for _ in range(m)]
min_heap = []
water_trapped = 0
# Push all the boundary cells into the heap
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(min_heap, (heightMap[i][j], i, j))
visited[i][j] = True
# Directions for neighbors (up, down, left, right)
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
# Process the cells using the min-heap
while min_heap:
height, x, y = heapq.heappop(min_heap)
# Check all 4 neighboring cells
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
# If the neighboring cell is lower, water can be trapped
if heightMap[nx][ny] < height:
water_trapped += height - heightMap[nx][ny]
# Mark the neighbor as visited and add it to the heap with the new boundary height
visited[nx][ny] = True
heapq.heappush(min_heap, (max(heightMap[nx][ny], height), nx, ny))
return water_trapped
🔍 Step-by-Step Explanation
1. Initialization of Min-Heap:
python
min_heap = []
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(min_heap, (heightMap[i][j], i, j))
visited[i][j] = True
- All the boundary cells are inserted into the min-heap because they are the starting points where water could potentially escape.
- We mark these boundary cells as visited to ensure they aren't processed multiple times.
2. Processing with Min-Heap:
python
while min_heap:
height, x, y = heapq.heappop(min_heap)
- We use the min-heap to always process the cell with the smallest height. This ensures that we expand from the lowest boundary.
3. Flooding the Neighboring Cells:
python
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
if heightMap[nx][ny] < height:
water_trapped += height - heightMap[nx][ny]
visited[nx][ny] = True
heapq.heappush(min_heap, (max(heightMap[nx][ny], height), nx, ny))
- For each cell being processed, we examine its four neighbors (up, down, left, right).
- If the neighboring cell is lower than the current cell, it means water can be trapped, and we add the difference to the total trapped water.
- The neighboring cell is then added to the heap with an updated height (to reflect the new boundary height after water is added).
4. Return the Result:
python
return water_trapped
- After processing all the cells, we return the total amount of water trapped.
💡 Example Walkthrough
Example 1:
python
Input:
heightMap = [
[1,4,3,1,3,2],
[3,2,1,3,2,4],
[2,3,3,2,3,1],
[6,4,3,2,1,5]
]
Output:
Output = 10
- Step 1: Initialize the min-heap with boundary cells and process the boundary cells.
- Step 2: Process the internal cells using the min-heap. Calculate the water trapped as we expand the boundary and check neighboring cells.
- Step 3: Return the total water trapped, which is 10 in this case.
⏱️ Time & Space Complexity
MetricComplexityTime ComplexityO(m * n log(m * n))Space ComplexityO(m * n)
- Time Complexity:
- Sorting the boundary cells and processing the internal cells involves inserting and removing cells from the min-heap. Each heap operation (insertion and removal) takes
O(log(m * n)), and we perform these operations for each cell, leading to a total time complexity of O(m * n log(m * n)), where m and n are the dimensions of the height map.
- Space Complexity:
- We use additional space for the min-heap, visited matrix, and the final trapped water result, resulting in a space complexity of
O(m * n).
🧵 Final Thoughts
LeetCode 407 is an excellent example of how to extend the classic "Trapping Rain Water" problem to 2D terrain using a priority queue and a greedy approach. By processing the lowest boundaries first and expanding from there, we can efficiently compute the trapped water. This problem tests your understanding of priority queues, greedy algorithms, and spatial reasoning with multi-dimensional grids.