407. Trapping Rain Water II
Problem Description
The challenge is to calculate the volume of water that could be trapped after raining on a 2D elevation map. The map is represented as a matrix where each cell's value indicates the height above some arbitrary baseline (e.g., sea level). The problem is quite analogous to trapping water in 3D space. Imagine each cell of the height map as a block that can trap water depending on the heights of the surrounding blocks. The goal is to determine the total amount of water that can be trapped by the elevation map after it has rained.
Intuition
The intuition behind the solution is to use a priority queue (or a min-heap) to keep track of the cells on the perimeter of the current water being trapped. Those cells effectively form a boundary, or a "wall," which dictates how much water can be contained inside them.
We can think of filling up a container with water; water will fill up from the borders inwards and will rise to the height of the shortest wall around it. In other words, the capacity of water at any point in our map is determined by the smallest height on its boundary.
To implement this:
- We initially add all the border cells to our priority queue since they cannot hold water and therefore set our initial boundary.
- Then, we continuously expand our water boundary inwards by considering the shortest wall (the wall with the minimum height) on our current boundary, which we obtain from our priority queue. Every time we choose a wall, we look at its adjacent cells.
- If any adjacent cell is shorter than the chosen wall, it means it's a candidate for holding water and the difference in height is the water it can contain.
- We then update the boundaries by adding the surrounding cells of the chosen wall to the priority queue. If the water can be trapped from those cells, it would be trapped at a height not lower than the tallest of walls we've encountered so far.
- This means each time we visit a new cell from the priority queue; we are assured that its capacity to hold water has been determined by the tallest wall around the cells that we've visited thus far.
Repeat this process until all cells have been visited, which ensures all cells that can trap water have been considered. The sum of all the trapped water gives us the result.
Learn more about Breadth-First Search and Heap (Priority Queue) patterns.
Which algorithm should you use to find a node that is close to the root of the tree?
Solution Approach
The solution leverages a min-heap (implemented in Python as a priority queue) to efficiently keep track of the current smallest height on the boundary, which represents a potential "wall" that can hold water.
Here is a step-by-step breakdown of the implementation:
-
Initialize Structures: A
visitedmatrix (same dimensions as the height map) is initialized to keep track of whether a cell has been processed. A priority queuepqis used to keep track of the boundary cells. We store tuples of(height, i, j)in the queue, whereheightis the cell's height, and(i, j)are the cell's coordinates on the map. -
Populate Priority Queue: Loop through all cells on the map. Mark border cells (the first and last row, the first and last column) as visited and push them onto the priority queue since they can't contain any water.
-
Process Internal Cells: Until the priority queue is empty, do the following: a. Pop the cell with the lowest height from our priority queue. This cell is part of the current lowest boundary. b. Check all four adjacent cells (using the directional offsets in
dirs). For each unvisited neighbor, calculate the potential water it could trap, which is the difference between the height of the popped cell and the neighbor's height, if the neighbor's height is less. c. If water can be trapped, add the volume to the answer (ans), and push the neighbor onto the priority queue with an updated height to reflect the maximum boundary height encountered so far. d. Mark the neighbor as visited. -
Return Result: Once the priority queue is empty, all cells that could hold water have been processed, and the
ansvariable contains the total volume of trapped water.
The use of a min-heap ensures that we always expand from the current lowest wall, and because we update visited cells with the maximum height encountered, we assure that any future water trapped will respect previous boundaries. This is similar to a "water level" rising to the height of the lowest enclosing boundary, ensuring that we don't miscalculate the volume by "spilling" over lower boundaries that haven't been considered yet.
Which of the following array represent a max heap?
Example Walkthrough
Let's consider a small 4x4 elevation map as an example:
1Height Map: 24 4 4 4 34 1 2 4 44 2 1 4 54 4 4 4
Following the solution approach for this elevation map:
-
Initialize Structures: Create a
visited2D matrix initialized withFalseand a priority queuepq. -
Populate Priority Queue: Add all border cells (first and last rows, and first and last columns) to the
pqand mark them as visited in thevisitedmatrix.- Initial
pq: [(4,0,0), (4,0,1), (4,0,2), (4,0,3), (4,1,0), (4,3,0), (4,1,3), (4,2,3), (4,3,1), (4,3,2), (4,3,3)]
- Initial
-
Process Internal Cells: Start popping cells from
pq. For example:a. Pop
(4,0,0)frompq. It's a border cell; no adjacent cells are unvisited or able to trap water.b. Continue popping border cells until we reach an internal cell. Let's say we now pop
(4,1,1).c. Check its neighbors: [(1,1,2), (1,2,1)]. These cells are lower than the current cell, so they can potentially hold water.
d. Calculate trapped water for each neighbor:
- For
(1,1,2)with height2, it could trap4 - 2 = 2units of water. - For
(1,2,1)with height2, it could trap4 - 2 = 2units of water.
e. Add neighbor cells to
pqwith updated heights showing the maximum wall height:- Add
(4,1,2)for(1,1,2)and mark as visited. - Add
(4,2,1)for(1,2,1)and mark as visited.
f. Continue this process with the new cells in the
pquntil no more cells can be visited. - For
-
Return Result: After processing all cells, we calculate that there is a total of
4units of trapped water (2 units above cell [1,2] and 2 units above cell [2,1]) in the map.
By using the priority queue to systematically expand the boundary and track the maximum wall height, we efficiently simulate the rise of water level and accurately calculate the total volume of trapped water.
Solution Implementation
1from heapq import heappop, heappush
2
3class Solution:
4 def trapRainWater(self, height_map: List[List[int]]) -> int:
5 # Get the dimensions of the map
6 rows, cols = len(height_map), len(height_map[0])
7
8 # Initialize a 2D visited array to keep track of processed cells
9 visited = [[False] * cols for _ in range(rows)]
10
11 # Priority Queue (min heap) to process the cells by height
12 min_heap = []
13
14 # Initialize the heap with the boundary cells and mark them as visited
15 for i in range(rows):
16 for j in range(cols):
17 if i == 0 or i == rows - 1 or j == 0 or j == cols - 1:
18 heappush(min_heap, (height_map[i][j], i, j))
19 visited[i][j] = True
20
21 # Total amount of trapped water
22 trapped_water = 0
23
24 # Directions for neighboring cells
25 directions = ((-1, 0), (0, 1), (1, 0), (0, -1))
26
27 # Process the cells until the heap is empty
28 while min_heap:
29 height, x, y = heappop(min_heap)
30 for dx, dy in directions:
31 nx, ny = x + dx, y + dy
32 # Check if the neighbor is within bounds and not visited
33 if 0 <= nx < rows and 0 <= ny < cols and not visited[nx][ny]:
34 # Calculate the possible water level difference
35 trapped_water += max(0, height - height_map[nx][ny])
36
37 # Mark the neighbor as visited
38 visited[nx][ny] = True
39
40 # Push the neighbor cell onto the heap with the max height
41 # to keep track of the 'water surface' level
42 heappush(min_heap, (max(height, height_map[nx][ny]), nx, ny))
43
44 # Return the total accumulated trapped water
45 return trapped_water
461import java.util.PriorityQueue;
2
3public class Solution {
4
5 // Method to calculate the total trapped rainwater in the given height map
6 public int trapRainWater(int[][] heightMap) {
7 int rows = heightMap.length, cols = heightMap[0].length;
8 boolean[][] visited = new boolean[rows][cols]; // Track visited cells
9 PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]); // Min-heap based on height
10
11 // Initialize the min-heap with the boundary cells and mark them as visited
12 for (int i = 0; i < rows; ++i) {
13 for (int j = 0; j < cols; ++j) {
14 if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
15 minHeap.offer(new int[]{heightMap[i][j], i, j});
16 visited[i][j] = true;
17 }
18 }
19 }
20
21 int totalWater = 0; // Variable to store total trapped water
22 // Direction vectors (up, right, down, left)
23 int[] dirX = {-1, 0, 1, 0};
24 int[] dirY = {0, 1, 0, -1};
25
26 // Process cells in the priority queue
27 while (!minHeap.isEmpty()) {
28 int[] current = minHeap.poll();
29 // Iterate over all four adjacent cells
30 for (int k = 0; k < 4; ++k) {
31 int newRow = current[1] + dirX[k], newCol = current[2] + dirY[k];
32
33 // Check bounds and visited status of the adjacent cell
34 if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol]) {
35 // Update total water based on the height difference
36 totalWater += Math.max(0, current[0] - heightMap[newRow][newCol]);
37 // Mark the adjacent cell as visited
38 visited[newRow][newCol] = true;
39 // Add the adjacent cell to the priority queue with the max border height
40 minHeap.offer(new int[]{Math.max(current[0], heightMap[newRow][newCol]), newRow, newCol});
41 }
42 }
43 }
44
45 return totalWater; // Return the total amount of trapped rainwater
46 }
47}
481class Solution {
2public:
3 int trapRainWater(vector<vector<int>>& height_map) {
4 // Define a tuple for priority queue to store the height and the coordinates
5 using HeightAndCoordinates = tuple<int, int, int>;
6
7 // Priority queue to store the boundary bars' height in ascending order
8 priority_queue<HeightAndCoordinates, vector<HeightAndCoordinates>, greater<HeightAndCoordinates>> min_heap;
9
10 // Get the dimensions of the height map
11 int rows = height_map.size(), cols = height_map[0].size();
12
13 // Visited matrix to keep track of the visited cells
14 vector<vector<bool>> visited(rows, vector<bool>(cols, false));
15
16 // Mark the boundary cells as visited and add them to the min_heap
17 for (int i = 0; i < rows; ++i) {
18 for (int j = 0; j < cols; ++j) {
19 if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
20 min_heap.emplace(height_map[i][j], i, j);
21 visited[i][j] = true;
22 }
23 }
24 }
25
26 // Initialize the water trapped accumulator to 0
27 int trapped_water = 0;
28
29 // Directions array to facilitate the traversal of adjacent cells
30 // Up, Right, Down, Left
31 const int directions[5] = {-1, 0, 1, 0, -1};
32
33 // Process cells until there are no more cells in the priority queue
34 while (!min_heap.empty()) {
35 auto [current_height, row, col] = min_heap.top();
36 min_heap.pop();
37
38 // Check all 4 possible directions
39 for (int k = 0; k < 4; ++k) {
40 int new_row = row + directions[k];
41 int new_col = col + directions[k + 1];
42
43 // Check if the new cell is within bounds and not visited
44 if (new_row >= 0 && new_row < rows && new_col >= 0 && new_col < cols && !visited[new_row][new_col]) {
45 // Update trapped water if the adjacent cell's height is less than the current cell's height
46 trapped_water += max(0, current_height - height_map[new_row][new_col]);
47
48 // Mark the cell as visited
49 visited[new_row][new_col] = true;
50
51 // Push the maximum height of the adjacent cell or current cell into the min_heap
52 min_heap.emplace(max(height_map[new_row][new_col], current_height), new_row, new_col);
53 }
54 }
55 }
56
57 // Return the total trapped water
58 return trapped_water;
59 }
60};
611// Define a type for the priority queue to store the height and the coordinates
2type HeightAndCoordinates = [number, number, number];
3
4// Function to trap rainwater using a height map
5function trapRainWater(heightMap: number[][]): number {
6 // Create a Min Heap to store boundary bars' height in ascending order
7 const minHeap: HeightAndCoordinates[] = [];
8
9 // Comparator function for Min Heap
10 const compare: (a: HeightAndCoordinates, b: HeightAndCoordinates) => number = ([heightA], [heightB]) => heightA - heightB;
11
12 // Helper function to heapify the minHeap
13 const heapify = (index: number) => {
14 let smallest = index;
15 const left = 2 * index + 1;
16 const right = 2 * index + 2;
17
18 if (left < minHeap.length && compare(minHeap[left], minHeap[smallest]) < 0) {
19 smallest = left;
20 }
21 if (right < minHeap.length && compare(minHeap[right], minHeap[smallest]) < 0) {
22 smallest = right;
23 }
24 if (smallest !== index) {
25 [minHeap[index], minHeap[smallest]] = [minHeap[smallest], minHeap[index]];
26 heapify(smallest);
27 }
28 };
29
30 // Helper function to extract the top element from the heap
31 const extractMin = (): HeightAndCoordinates | undefined => {
32 if (minHeap.length === 0) return undefined;
33 const min = minHeap[0];
34 minHeap[0] = minHeap[minHeap.length - 1];
35 minHeap.pop();
36 heapify(0);
37 return min;
38 };
39
40 // Helper function to insert elements in the heap
41 const insertHeap = (element: HeightAndCoordinates) => {
42 minHeap.push(element);
43 let i = minHeap.length - 1;
44 while (i !== 0 && compare(minHeap[Math.floor((i - 1) / 2)], minHeap[i]) > 0) {
45 [minHeap[i], minHeap[Math.floor((i - 1) / 2)]] = [minHeap[Math.floor((i - 1) / 2)], minHeap[i]];
46 i = Math.floor((i - 1) / 2);
47 }
48 };
49
50 const rows: number = heightMap.length;
51 const cols: number = heightMap[0].length;
52
53 // Visited matrix to keep track of visited cells
54 const visited: boolean[][] = Array.from(new Array(rows), () => new Array(cols).fill(false));
55
56 // Mark the boundary cells as visited and add them to the minHeap
57 for (let i = 0; i < rows; i++) {
58 for (let j = 0; j < cols; j++) {
59 if (i === 0 || i === rows - 1 || j === 0 || j === cols - 1) {
60 insertHeap([heightMap[i][j], i, j]);
61 visited[i][j] = true;
62 }
63 }
64 }
65
66 // Initialize the accumulator for the trapped water to 0
67 let trappedWater: number = 0;
68
69 // Directions array to facilitate traversal of adjacent cells (up, right, down, left)
70 const directions: number[] = [-1, 0, 1, 0, -1];
71
72 // Process cells until the priority queue is empty
73 while (minHeap.length) {
74 const [currentHeight, row, col] = extractMin()!;
75
76 // Check all 4 potential directions
77 for (let k = 0; k < 4; k++) {
78 const newRow: number = row + directions[k];
79 const newCol: number = col + directions[k + 1];
80
81 // Check if the new cell is within bounds and has not been visited
82 if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && !visited[newRow][newCol]) {
83 // Update trapped water if the adjacent cell's height is less than the current height
84 trappedWater += Math.max(0, currentHeight - heightMap[newRow][newCol]);
85
86 // Mark the cell as visited
87 visited[newRow][newCol] = true;
88
89 // Add the maximum height of the adjacent or current cell to the minHeap
90 insertHeap([Math.max(heightMap[newRow][newCol], currentHeight), newRow, newCol]);
91 }
92 }
93 }
94
95 // Return total trapped water
96 return trappedWater;
97}
98What data structure does Breadth-first search typically uses to store intermediate states?
Time and Space Complexity
The time complexity of the code is O(M*N*log(M+N)). This is because the code uses a min-heap to keep track of the boundary cells of the height map which could potentially store at most O(M+N) elements (the perimeter of the map). Each cell is pushed and popped exactly once from the priority queue (since visited cells are marked and not revisited) resulting in O(log(M+N)) for each push and pop operation and there are M*N cells.
The space complexity of the code is O(M*N). This is due to two factors. First is the priority queue, which can grow up to the number of boundary cells, which is O(M+N) in the worst case. Second is the visited matrix vis, which is of size M*N. As M*N is typically larger than M+N for non-trivial maps, the overall space complexity is dominated by the vis matrix.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.