407. Trapping Rain Water II
Problem Description
Given an m x n integer matrix heightMap representing the height of each unit cell in a 2D elevation map, return the volume of water it can trap after raining.
Example 1:
Input: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
Output: 4
Explanation: After the rain, water is trapped between the blocks.
We have two small ponds 1 and 3 units trapped.
The total volume of water trapped is 4.Example 2:
Input: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
Output: 10Constraints:
m == heightMap.lengthn == heightMap[i].length1 <= m, n <= 2000 <= heightMap[i][j] <= 2 * 10⁴
Solution
Python Solution
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])
if m < 3 or n < 3:
return 0
# Initialize visited array and priority queue
visited = [[False] * n for _ in range(m)]
heap = []
# Add border cells to heap
for i in range(m):
heapq.heappush(heap, (heightMap[i][0], i, 0))
heapq.heappush(heap, (heightMap[i][n-1], i, n-1))
visited[i][0] = visited[i][n-1] = True
for j in range(1, n-1):
heapq.heappush(heap, (heightMap[0][j], 0, j))
heapq.heappush(heap, (heightMap[m-1][j], m-1, j))
visited[0][j] = visited[m-1][j] = True
# Process cells from lowest to highest
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
water = 0
max_height = 0
while heap:
height, i, j = heapq.heappop(heap)
max_height = max(max_height, height)
# Check all adjacent cells
for di, dj in directions:
ni, nj = i + di, j + dj
if (0 <= ni < m and 0 <= nj < n and not visited[ni][nj]):
visited[ni][nj] = True
if heightMap[ni][nj] < max_height:
water += max_height - heightMap[ni][nj]
heapq.heappush(heap, (heightMap[ni][nj], ni, nj))
return waterTime Complexity: O(mn log(m+n))
Where m and n are the dimensions of the heightMap. Each cell is pushed and popped from the heap once.
Space Complexity: O(mn)
For the visited array and the heap.
Java Solution
class Solution {
private static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int trapRainWater(int[][] heightMap) {
if (heightMap == null || heightMap.length < 3 || heightMap[0].length < 3) {
return 0;
}
int m = heightMap.length, n = heightMap[0].length;
PriorityQueue| heap = new PriorityQueue<>((a, b) -> a.height - b.height);
boolean[][] visited = new boolean[m][n];
// Add border cells
for (int i = 0; i < m; i++) {
heap.offer(new Cell(i, 0, heightMap[i][0]));
heap.offer(new Cell(i, n-1, heightMap[i][n-1]));
visited[i][0] = visited[i][n-1] = true;
}
for (int j = 1; j < n-1; j++) {
heap.offer(new Cell(0, j, heightMap[0][j]));
heap.offer(new Cell(m-1, j, heightMap[m-1][j]));
visited[0][j] = visited[m-1][j] = true;
}
// Process cells
int water = 0;
int maxHeight = 0;
while (!heap.isEmpty()) {
Cell cell = heap.poll();
maxHeight = Math.max(maxHeight, cell.height);
for (int[] dir : DIRECTIONS) {
int ni = cell.row + dir[0];
int nj = cell.col + dir[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
visited[ni][nj] = true;
if (heightMap[ni][nj] < maxHeight) {
water += maxHeight - heightMap[ni][nj];
}
heap.offer(new Cell(ni, nj, heightMap[ni][nj]));
}
}
}
return water;
}
private static class Cell {
int row, col, height;
Cell(int row, int col, int height) {
this.row = row;
this.col = col;
this.height = height;
}
}
} | Time Complexity: O(mn log(m+n))
Where m and n are the dimensions of the heightMap. Each cell is pushed and popped from the heap once.
Space Complexity: O(mn)
For the visited array and the heap.
C++ Solution
class Solution {
private:
const vector> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public:
int trapRainWater(vector>& heightMap) {
if (heightMap.size() < 3 || heightMap[0].size() < 3) {
return 0;
}
int m = heightMap.size(), n = heightMap[0].size();
vector> visited(m, vector(n, false));
// Min heap of {height, row, col}
priority_queue, vector>, greater<>> heap;
// Add border cells
for (int i = 0; i < m; i++) {
heap.push({heightMap[i][0], i, 0});
heap.push({heightMap[i][n-1], i, n-1});
visited[i][0] = visited[i][n-1] = true;
}
for (int j = 1; j < n-1; j++) {
heap.push({heightMap[0][j], 0, j});
heap.push({heightMap[m-1][j], m-1, j});
visited[0][j] = visited[m-1][j] = true;
}
// Process cells
int water = 0;
int maxHeight = 0;
while (!heap.empty()) {
auto [height, i, j] = heap.top();
heap.pop();
maxHeight = max(maxHeight, height);
for (const auto& [di, dj] : directions) {
int ni = i + di, nj = j + dj;
if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
visited[ni][nj] = true;
if (heightMap[ni][nj] < maxHeight) {
water += maxHeight - heightMap[ni][nj];
}
heap.push({heightMap[ni][nj], ni, nj});
}
}
}
return water;
}
}; Time Complexity: O(mn log(m+n))
Where m and n are the dimensions of the heightMap. Each cell is pushed and popped from the heap once.
Space Complexity: O(mn)
For the visited array and the heap.
JavaScript Solution
/**
* @param {number[][]} heightMap
* @return {number}
*/
var trapRainWater = function(heightMap) {
if (heightMap.length < 3 || heightMap[0].length < 3) {
return 0;
}
const m = heightMap.length, n = heightMap[0].length;
const visited = Array(m).fill().map(() => Array(n).fill(false));
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
// Min heap implementation
const heap = new MinHeap();
// Add border cells
for (let i = 0; i < m; i++) {
heap.push([heightMap[i][0], i, 0]);
heap.push([heightMap[i][n-1], i, n-1]);
visited[i][0] = visited[i][n-1] = true;
}
for (let j = 1; j < n-1; j++) {
heap.push([heightMap[0][j], 0, j]);
heap.push([heightMap[m-1][j], m-1, j]);
visited[0][j] = visited[m-1][j] = true;
}
// Process cells
let water = 0;
let maxHeight = 0;
while (!heap.isEmpty()) {
const [height, i, j] = heap.pop();
maxHeight = Math.max(maxHeight, height);
for (const [di, dj] of directions) {
const ni = i + di, nj = j + dj;
if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni][nj]) {
visited[ni][nj] = true;
if (heightMap[ni][nj] < maxHeight) {
water += maxHeight - heightMap[ni][nj];
}
heap.push([heightMap[ni][nj], ni, nj]);
}
}
}
return water;
};
class MinHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this.bubbleUp(this.heap.length - 1);
}
pop() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) return this.heap.pop();
const result = this.heap[0];
this.heap[0] = this.heap.pop();
this.bubbleDown(0);
return result;
}
isEmpty() {
return this.heap.length === 0;
}
bubbleUp(index) {
while (index > 0) {
const parentIndex = Math.floor((index - 1) / 2);
if (this.heap[parentIndex][0] <= this.heap[index][0]) break;
[this.heap[parentIndex], this.heap[index]] =
[this.heap[index], this.heap[parentIndex]];
index = parentIndex;
}
}
bubbleDown(index) {
while (true) {
let smallest = index;
const leftChild = 2 * index + 1;
const rightChild = 2 * index + 2;
if (leftChild < this.heap.length &&
this.heap[leftChild][0] < this.heap[smallest][0]) {
smallest = leftChild;
}
if (rightChild < this.heap.length &&
this.heap[rightChild][0] < this.heap[smallest][0]) {
smallest = rightChild;
}
if (smallest === index) break;
[this.heap[index], this.heap[smallest]] =
[this.heap[smallest], this.heap[index]];
index = smallest;
}
}
}Time Complexity: O(mn log(m+n))
Where m and n are the dimensions of the heightMap. Each cell is pushed and popped from the heap once.
Space Complexity: O(mn)
For the visited array and the heap.
C# Solution
public class Solution {
private static readonly (int, int)[] Directions = {(0, 1), (0, -1), (1, 0), (-1, 0)};
public int TrapRainWater(int[][] heightMap) {
if (heightMap == null || heightMap.Length < 3 || heightMap[0].Length < 3) {
return 0;
}
int m = heightMap.Length, n = heightMap[0].Length;
var visited = new bool[m, n];
var heap = new PriorityQueue<(int row, int col, int height)>();
// Add border cells
for (int i = 0; i < m; i++) {
heap.Enqueue((i, 0, heightMap[i][0]));
heap.Enqueue((i, n-1, heightMap[i][n-1]));
visited[i, 0] = visited[i, n-1] = true;
}
for (int j = 1; j < n-1; j++) {
heap.Enqueue((0, j, heightMap[0][j]));
heap.Enqueue((m-1, j, heightMap[m-1][j]));
visited[0, j] = visited[m-1, j] = true;
}
// Process cells
int water = 0;
int maxHeight = 0;
while (heap.Count > 0) {
var (i, j, height) = heap.Dequeue();
maxHeight = Math.Max(maxHeight, height);
foreach (var (di, dj) in Directions) {
int ni = i + di, nj = j + dj;
if (ni >= 0 && ni < m && nj >= 0 && nj < n && !visited[ni, nj]) {
visited[ni, nj] = true;
if (heightMap[ni][nj] < maxHeight) {
water += maxHeight - heightMap[ni][nj];
}
heap.Enqueue((ni, nj, heightMap[ni][nj]));
}
}
}
return water;
}
private class PriorityQueue where T : struct {
private readonly List _heap = new List();
public int Count => _heap.Count;
public void Enqueue(T item) {
_heap.Add(item);
BubbleUp(_heap.Count - 1);
}
public T Dequeue() {
var result = _heap[0];
_heap[0] = _heap[_heap.Count - 1];
_heap.RemoveAt(_heap.Count - 1);
if (_heap.Count > 0) BubbleDown(0);
return result;
}
private void BubbleUp(int index) {
while (index > 0) {
int parent = (index - 1) / 2;
if (Compare(_heap[parent], _heap[index]) <= 0) break;
Swap(parent, index);
index = parent;
}
}
private void BubbleDown(int index) {
while (true) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < _heap.Count && Compare(_heap[left], _heap[smallest]) < 0)
smallest = left;
if (right < _heap.Count && Compare(_heap[right], _heap[smallest]) < 0)
smallest = right;
if (smallest == index) break;
Swap(index, smallest);
index = smallest;
}
}
private void Swap(int i, int j) {
var temp = _heap[i];
_heap[i] = _heap[j];
_heap[j] = temp;
}
private int Compare(T a, T b) {
return ((ValueTuple)a).Item3.CompareTo(((ValueTuple)b).Item3);
}
}
} Time Complexity: O(mn log(m+n))
Where m and n are the dimensions of the heightMap. Each cell is pushed and popped from the heap once.
Space Complexity: O(mn)
For the visited array and the heap.
Approach Explanation
The solution uses a priority queue (min heap) approach:
- Key Insights:
- Border processing
- Height tracking
- Water accumulation
- Priority queue
- Algorithm Steps:
- Initialize borders
- Process cells
- Track water
- Update heights
Implementation Details:
- Min heap usage
- Cell processing
- Height tracking
- Water calculation
Optimization Insights:
- Border handling
- Early termination
- Memory usage
- Efficient traversal
Edge Cases:
- Small grid
- No water
- Maximum height
- Border conditions