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.
Flowchart Walkthrough
Let's utilize the algorithm flowchart to determine the appropriate strategy for solving the problem described in LeetCode 407, Trapping Rain Water II. Here's how the analysis goes based on the flowchart structure:
Is it a graph?
- Yes: Although it's a 2D height map, it can be viewed as a graph where every cell is a node connected to its adjacent cells, and the edges can have weights corresponding to the height differences.
Is it a tree?
- No: This graph isn't a hierarchical tree structure because each cell could potentially connect to multiple other cells without a single parent-child relationship.
Is the problem related to directed acyclic graphs (DAGs)?
- No: In this scenario, the graph can actually have cycles due to the possible connections in multiple directions.
Is the problem related to shortest paths?
- Yes: Though it's not about finding a path between two points, the solution involves propagating water level increments from the borders towards the center, which can be thought of as calculating a form of path to fill water to various points optimally.
Is the graph weighted?
- Yes: The graph weights can be considered as the height differences between cells that impact the water trapping calculation.
Conclusion: For a problem like Trapping Rain Water II, where calculations involve a weighted graph to find an optimized "filling" strategy based on heights, Breadth-First Search (BFS) adapted for weighted scenarios (like in a priority queue) is typically utilized. This BFS version ensures that cells at lower heights are processed first, which matches the requirement to handle the lows in the height map before the highs to determine trapped water accurately.
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.
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
visited
matrix (same dimensions as the height map) is initialized to keep track of whether a cell has been processed. A priority queuepq
is used to keep track of the boundary cells. We store tuples of(height, i, j)
in the queue, whereheight
is 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
ans
variable 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
visited
2D matrix initialized withFalse
and a priority queuepq
. -
Populate Priority Queue: Add all border cells (first and last rows, and first and last columns) to the
pq
and mark them as visited in thevisited
matrix.- 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 = 2
units of water. - For
(1,2,1)
with height2
, it could trap4 - 2 = 2
units of water.
e. Add neighbor cells to
pq
with 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
pq
until no more cells can be visited. - For
-
Return Result: After processing all cells, we calculate that there is a total of
4
units 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
46
1import 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}
48
1class 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};
61
1// 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}
98
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 technique can we use to find the middle of a linked list?
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
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.