42. Trapping Rain Water
Problem Description
Imagine you have a side-view silhouette of a series of blocks with various heights. These blocks represent the elevation map in the problem. When it rains, water will fill in the gaps between these blocks. The water can be trapped between the elevations where the adjacent blocks are higher. The width of each block is 1
unit. The task is to calculate the total amount of water that these blocks can hold without spilling over, after a rainfall.
To tackle this, picture placing water on top of the blocks. Some water will be trapped between taller blocks, while some will flow off the sides if there are no sufficient barriers. The amount of trapped water at any point depends on the tallest blocks to its left and to its right because these will act as barriers. At any given point, the amount of water that can be held above it is the difference between the height of the shorter of the two barriers (either left or right) and the height of the block itself.
Intuition
The solution to this problem is based on the observation that the amount of water above a bar is determined by the highest bar to the left and the highest bar to the right. No matter what the arrangements of other bars are, the water above a given bar can never exceed the height difference between the bar and the shortest of the two highest bars flanking it.
To approach this problem efficiently, we use dynamic programming. We create two arrays, left
and right
, which represent the highest bars up to that point from the left and right, respectively. These arrays are populated by traversing the height array twice— once from left to right, updating the left
array with the maximum height seen so far, and once from right to left, updating the right
array similarly.
Once we have these two arrays, the amount of water above each bar is simply the difference between it and the minimum of the highest bars to its left and right. The solution is then to accumulate this difference for each bar to get the total amount of trapped water.
To put it more concretely, the left[i]
array gets updated as we go, ensuring that at each step i
, we have the height of the tallest bar up to that point. The right[i]
array does the same but in the opposite direction. When calculating the trapped water at index i
, we look at min(left[i], right[i])
which gives us the maximum water level possible at that point. Then, we subtract the height of the current bar height[i]
to know how much water can actually be trapped there. Summing these values together for all indices gives us the total amount of trapped water.
Learn more about Stack, Two Pointers, Dynamic Programming and Monotonic Stack patterns.
Solution Approach
The solution uses a combination of arrays and iteration to calculate the volume of trapped rainwater.
Firstly, we define two arrays, left
and right
:
left[i]
contains the height of the tallest pillar to the left of the position with indexi
, including the pillar ati
itself.right[i]
contains the height of the tallest pillar to the right of the position with indexi
, also including the pillar ati
.
We initialize left[0]
with the height of the first pillar height[0]
, since there's nothing to its left. Similarly, we initialize right[n-1]
(where n
is the number of pillars) with the height of the last pillar height[n-1]
.
Next, two separate loops are used to populate these arrays:
-
For
left[i]
, starting fromi=1
and moving towards the end of the array, we calculate the maximum height encountered so far usingmax(left[i - 1], height[i])
and store it inleft[i]
. This ensures thatleft[i]
contains the height of the tallest bar to the left including the current bar. -
For
right[i]
, we move in the opposite direction, starting fromi=n-2
down to0
. We updateright[i]
withmax(right[i + 1], height[i])
. This accomplishes the same as theleft
array but for bars to the right.
With these arrays filled, we can then iterate through each index i
and calculate the trapped water above the bar at i
. The amount of trapped water here is min(left[i], right[i]) - height[i]
because it is bounded by the shortest of the two tallest pillars on either side.
Finally, we sum up the calculated trapped water values for all i
to find the total amount of trapped rainwater. The result is computed using sum(min(l, r) - h for l, r, h in zip(left, right, height))
, taking advantage of Python's built-in functions and list comprehensions for concise code. By zipping the left
, right
, and height
arrays together, we can iterate over them simultaneously, allowing us to easily calculate the minimum of left[i]
and right[i]
, subtract the height[i]
, and sum all these values.
Throughout this process, we use simple arrays and loops, a technique that falls under the category of dynamic programming, where we break down the problem into simpler subproblems and iteratively build up solutions to larger problems leveraging the solutions to smaller problems.
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 take a small example to illustrate the solution approach:
Suppose our height map for the blocks is given by height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
.
Now, follow the steps below:
Firstly, we initialize our left
and right
arrays:
- Initialize
left
array with the same length asheight
withleft[0] = height[0]
, which is0
. - Initialize
right
array with the same length asheight
withright[-1] = height[-1]
, which is1
.
Secondly, we populate the left
and right
arrays:
- Start filling the
left
array fromleft[1]
toleft[-1]
. For eachleft[i]
, we considermax(left[i - 1], height[i])
. This updatesleft
to[0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]
. - Fill the
right
array in reverse (starting from the second to last element and moving to the first). For eachright[i]
, we considermax(right[i + 1], height[i])
. This updatesright
to[3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]
.
With both arrays filled, we now calculate the trapped water above each index i
in the height
array:
- For each position
i
, calculate the trapped water asmin(left[i], right[i]) - height[i]
, which gives us the volume at each position as[0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0]
.
Lastly, sum the trapped water calculated for every position:
- Calculate the sum which is
0 + 0 + 1 + 0 + 1 + 2 + 1 + 0 + 0 + 1 + 0 + 0
, giving us a total of6
units of water that the blocks can hold after rainfall.
By following the described solution approach step by step, we easily solve the problem using dynamic programming concepts and determine that our example silhouette can trap a total of 6 units of water.
Solution Implementation
1from typing import List
2
3class Solution:
4 def trap(self, height: List[int]) -> int:
5 # Find the number of elements in height.
6 num_elements = len(height)
7
8 # Initialize arrays to store the maximum to the left and right of each element.
9 max_left = [height[0]] * num_elements
10 max_right = [height[-1]] * num_elements
11
12 # Fill the max_left array with the maximum height to the left of each element.
13 for i in range(1, num_elements):
14 max_left[i] = max(max_left[i - 1], height[i])
15
16 # Fill the max_right array with the maximum height to the right of each element.
17 for i in range(num_elements - 2, -1, -1):
18 max_right[i] = max(max_right[i + 1], height[i])
19
20 # Calculate the total amount of trapped water using the height difference
21 # between the minimum of max_left and max_right for each element and the height at that element.
22 trapped_water = sum(min(max_left[i], max_right[i]) - height[i] for i in range(num_elements))
23
24 # Return the total amount of trapped water.
25 return trapped_water
26
1class Solution {
2 public int trap(int[] height) {
3 // The length of the given height array.
4 int length = height.length;
5
6 // Arrays to store the maximum height to the left and right of every bar.
7 int[] maxLeft = new int[length];
8 int[] maxRight = new int[length];
9
10 // Initialize the first element of maxLeft with the first height
11 // as there's nothing to the left of it.
12 maxLeft[0] = height[0];
13 // Initialize the last element of maxRight with the last height
14 // as there's nothing to the right of it.
15 maxRight[length - 1] = height[length - 1];
16
17 // Populate the maxLeft array by finding the maximum height to the left
18 // of the current position, including itself.
19 for (int i = 1; i < length; ++i) {
20 maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
21 }
22
23 // Populate the maxRight array by finding the maximum height to the right
24 // of the current position, including itself. This loop runs backwards.
25 for (int i = length - 2; i >= 0; --i) {
26 maxRight[i] = Math.max(maxRight[i + 1], height[i]);
27 }
28
29 // Variable to store the total amount of trapped water.
30 int totalWater = 0;
31
32 // Calculate the trapped water at each position by finding the
33 // minimum of maxLeft and maxRight at that position (which is the maximum
34 // water level the position can hold) and subtracting the height of the bar.
35 for (int i = 0; i < length; ++i) {
36 totalWater += Math.min(maxLeft[i], maxRight[i]) - height[i];
37 }
38
39 // Return the total trapped water.
40 return totalWater;
41 }
42}
43
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 int trap(vector<int>& height) {
7 int num_elements = height.size(); // Number of elements in the height vector
8
9 // Handling edge case: if the height vector is empty or has only one bar,
10 // no water can be trapped.
11 if(num_elements < 2) {
12 return 0;
13 }
14
15 vector<int> left_max(num_elements), right_max(num_elements); // Initialize vectors to store the max height to the left and right of each element
16
17 // Base case: The first element's left max will be itself and
18 // the last element's right max will be itself
19 left_max[0] = height[0];
20 right_max[num_elements - 1] = height[num_elements - 1];
21
22 // Fill left_max array such that left_max[i] contains highest bar height to the left of index 'i' including itself
23 for (int i = 1; i < num_elements; ++i) {
24 left_max[i] = max(left_max[i - 1], height[i]);
25 }
26
27 // Fill right_max array such that right_max[i] contains highest bar height to the right of index 'i' including itself
28 for (int i = num_elements - 2; i >= 0; --i) {
29 right_max[i] = max(right_max[i + 1], height[i]);
30 }
31
32 int total_water = 0; // Initialize total water to be trapped
33
34 // Calculate trapped water at each index 'i' by finding the
35 // smaller of the left and right max bars and subtracting the current height.
36 // The result is added to total_water to find the cumulative water trapped across the entire array.
37 for (int i = 0; i < num_elements; ++i) {
38 total_water += min(left_max[i], right_max[i]) - height[i];
39 }
40
41 // Return the total amount of trapped water
42 return total_water;
43 }
44};
45
1function trap(heights: number[]): number {
2 const numElements = heights.length;
3 // Initialize arrays to store the maximum height to the left/right of each index
4 const maxLeftHeights: number[] = new Array(numElements).fill(heights[0]);
5 const maxRightHeights: number[] = new Array(numElements).fill(heights[numElements - 1]);
6
7 // Populate the maxLeftHeights array with the maximum heights to the left of each index
8 for (let i = 1; i < numElements; ++i) {
9 maxLeftHeights[i] = Math.max(maxLeftHeights[i - 1], heights[i]);
10 }
11
12 // Populate the maxRightHeights array with the maximum heights to the right of each index
13 for (let i = numElements - 2; i >= 0; --i) {
14 maxRightHeights[i] = Math.max(maxRightHeights[i + 1], heights[i]);
15 }
16
17 // Calculate the total amount of trapped water
18 let totalWaterTrapped = 0;
19 for (let i = 0; i < numElements; ++i) {
20 // The water level at the current index is the minimum of the max heights to the left and right
21 // Subtract the height of the current bar to get the water trapped at this index
22 totalWaterTrapped += Math.min(maxLeftHeights[i], maxRightHeights[i]) - heights[i];
23 }
24
25 return totalWaterTrapped;
26}
27
Time and Space Complexity
The provided code implements a solution to calculate the amount of water that can be trapped between the bars of different heights represented by the height
list.
Time complexity: The time complexity of the solution is O(n)
where n
is the number of elements in the height
list. The reasoning behind this time complexity is as follows:
- Creating the
left
andright
lists takesO(n)
each as they are initialized based on the first and last element respectively. - Populating the
left
andright
lists with the maximum height encountered so far from the left and right involves a single pass through theheight
list from left to right and right to left, which again takesO(n)
time each. - Finally, the
sum(min(l, r) - h for l, r, h in zip(left, right, height))
computation is also linear, as it involves a single pass through the zipped lists, for a total ofO(n)
time.
Overall, as all these steps are sequential and each of them takes O(n)
time, the total time complexity is O(n)
.
Space complexity: The space complexity of the solution is also O(n)
. This is because additional space is used to store the left
and right
lists which both have the same length as the input list height
. No other significant storage is used that depends on n
(the length of the height
list), therefore, the space complexity is O(n)
.
To summarize, the code provided efficiently computes the water trapping problem with a linear time complexity and uses linear space to store interim results.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
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.