42. Trapping Rain Water
Problem Description
You are given an array of n
non-negative integers where each integer represents the height of a bar in an elevation map. Each bar has a width of 1 unit. Your task is to calculate how much rainwater can be trapped between the bars after it rains.
The water gets trapped between bars when there are taller bars on both sides that can act as walls. For any position i
, water can be trapped above it if there exists a taller bar somewhere to its left and another taller bar somewhere to its right. The amount of water that can be trapped at position i
is determined by the minimum height of the tallest bars on both sides minus the height of the current bar.
For example, if you have heights [0,1,0,2,1,0,1,3,2,1,2,1]
, the total trapped water would be 6 units. Water fills in the valleys created by the elevation differences, but only up to the level constrained by the shorter of the two surrounding peaks.
The solution uses dynamic programming to pre-compute two arrays:
left[i]
: stores the maximum height from the start up to positioni
right[i]
: stores the maximum height from positioni
to the end
For each position, the water level above it is min(left[i], right[i])
, and the actual water trapped is min(left[i], right[i]) - height[i]
. The total trapped water is the sum of water at all positions.
Intuition
To understand how water gets trapped, imagine looking at each bar individually. At any given position, water can only be held if there are taller "walls" on both sides. The water level at that position will be determined by the shorter of these two walls - water would overflow from the shorter side if we tried to fill it higher.
Think of it like filling a bathtub - the water level can't exceed the height of the lowest wall. For each position i
, we need to know:
- What's the tallest bar to my left (including myself)?
- What's the tallest bar to my right (including myself)?
The water level above position i
would be min(max_left, max_right)
. Since the bar itself takes up space, the actual water trapped is min(max_left, max_right) - height[i]
.
The key insight is that we can pre-compute these maximum heights efficiently. Instead of checking all bars to the left and right for each position (which would be inefficient), we can build two arrays in linear time:
- Build
left[]
by scanning from left to right, whereleft[i] = max(left[i-1], height[i])
- Build
right[]
by scanning from right to left, whereright[i] = max(right[i+1], height[i])
This way, we calculate each maximum only once and reuse the results. The pattern here is that the maximum height up to position i
is either the bar at position i
itself or the maximum we've seen so far before position i
. This dynamic programming approach reduces our time complexity from O(n²)
to O(n)
.
Learn more about Stack, Two Pointers, Dynamic Programming and Monotonic Stack patterns.
Solution Approach
The implementation uses dynamic programming with two auxiliary arrays to efficiently compute the trapped water.
Step 1: Initialize the arrays
- Create
left
array initialized withheight[0]
repeatedn
times - Create
right
array initialized withheight[-1]
repeatedn
times - These arrays will store the maximum heights from left and right respectively
Step 2: Build the maximum height arrays
The algorithm fills both arrays in a single loop from i = 1
to n-1
:
-
For
left[i]
: Calculatemax(left[i-1], height[i])
- This gives us the maximum height from position 0 to position
i
- We build this left-to-right since each position depends on the previous one
- This gives us the maximum height from position 0 to position
-
For
right[n-i-1]
: Calculatemax(right[n-i], height[n-i-1])
- This gives us the maximum height from position
n-i-1
to positionn-1
- We build this right-to-left by using index manipulation
n-i-1
- This gives us the maximum height from position
Step 3: Calculate trapped water
Using Python's zip()
function to iterate through all three arrays simultaneously:
- For each position, calculate
min(left[i], right[i]) - height[i]
min(left[i], right[i])
gives the water level at positioni
- Subtracting
height[i]
gives the actual water trapped above the bar - Sum all these values to get the total trapped water
Time Complexity: O(n)
- We make two passes through the array (one for building the arrays, one for calculating the sum)
Space Complexity: O(n)
- We use two additional arrays of size n
to store the maximum heights
The elegance of this solution lies in pre-computing the required information, allowing us to calculate the trapped water at each position in constant time during the final summation.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example with heights [3, 0, 2, 0, 4]
to see how the solution works.
Initial Setup:
- Array:
[3, 0, 2, 0, 4]
- n = 5
- Initialize
left = [3, 3, 3, 3, 3]
(all set to height[0]) - Initialize
right = [4, 4, 4, 4, 4]
(all set to height[-1])
Step 1: Build the maximum height arrays
Building left[]
(max height from left up to position i):
- i = 1:
left[1] = max(left[0], height[1]) = max(3, 0) = 3
- i = 2:
left[2] = max(left[1], height[2]) = max(3, 2) = 3
- i = 3:
left[3] = max(left[2], height[3]) = max(3, 0) = 3
- i = 4:
left[4] = max(left[3], height[4]) = max(3, 4) = 4
- Result:
left = [3, 3, 3, 3, 4]
Building right[]
(max height from position i to the end):
- i = 1, pos = 3:
right[3] = max(right[4], height[3]) = max(4, 0) = 4
- i = 2, pos = 2:
right[2] = max(right[3], height[2]) = max(4, 2) = 4
- i = 3, pos = 1:
right[1] = max(right[2], height[1]) = max(4, 0) = 4
- i = 4, pos = 0:
right[0] = max(right[1], height[0]) = max(4, 3) = 4
- Result:
right = [4, 4, 4, 4, 4]
Step 2: Calculate trapped water at each position
For each position, water trapped = min(left[i], right[i]) - height[i]
:
Position | height | left | right | min(left, right) | Water Trapped |
---|---|---|---|---|---|
0 | 3 | 3 | 4 | 3 | 3 - 3 = 0 |
1 | 0 | 3 | 4 | 3 | 3 - 0 = 3 |
2 | 2 | 3 | 4 | 3 | 3 - 2 = 1 |
3 | 0 | 3 | 4 | 3 | 3 - 0 = 3 |
4 | 4 | 4 | 4 | 4 | 4 - 4 = 0 |
Total water trapped = 0 + 3 + 1 + 3 + 0 = 7 units
Visual representation:
| |≈≈≈| |≈≈≈|≈|≈| |≈|≈|≈|≈| |_|_|_|_| 3 0 2 0 4
Where ≈
represents trapped water. The water fills the valleys between the bars, with the level capped by the minimum of the tallest bars on each side.
Solution Implementation
1class Solution:
2 def trap(self, height: List[int]) -> int:
3 """
4 Calculate the amount of water that can be trapped after raining.
5
6 Args:
7 height: List of non-negative integers representing elevation map
8
9 Returns:
10 Total amount of trapped rainwater
11 """
12 n = len(height)
13
14 # Initialize arrays to store maximum height to the left and right of each position
15 left_max = [0] * n
16 right_max = [0] * n
17
18 # Base cases: first element for left_max, last element for right_max
19 left_max[0] = height[0]
20 right_max[n - 1] = height[n - 1]
21
22 # Fill left_max array: for each position, store the maximum height seen so far from the left
23 for i in range(1, n):
24 left_max[i] = max(left_max[i - 1], height[i])
25
26 # Fill right_max array: for each position, store the maximum height seen so far from the right
27 for i in range(n - 2, -1, -1):
28 right_max[i] = max(right_max[i + 1], height[i])
29
30 # Calculate trapped water at each position
31 # Water level at position i = min(left_max[i], right_max[i])
32 # Trapped water = water level - height of bar at position i
33 total_water = 0
34 for i in range(n):
35 water_level = min(left_max[i], right_max[i])
36 total_water += water_level - height[i]
37
38 return total_water
39
1class Solution {
2 public int trap(int[] height) {
3 // Get the length of the height array
4 int n = height.length;
5
6 // Arrays to store the maximum height to the left and right of each position
7 int[] leftMax = new int[n];
8 int[] rightMax = new int[n];
9
10 // Initialize the first element of leftMax and last element of rightMax
11 leftMax[0] = height[0];
12 rightMax[n - 1] = height[n - 1];
13
14 // Fill both arrays in a single pass
15 // leftMax[i] stores the maximum height from index 0 to i
16 // rightMax[i] stores the maximum height from index i to n-1
17 for (int i = 1; i < n; i++) {
18 leftMax[i] = Math.max(leftMax[i - 1], height[i]);
19 rightMax[n - i - 1] = Math.max(rightMax[n - i], height[n - i - 1]);
20 }
21
22 // Calculate the total trapped water
23 int totalWater = 0;
24 for (int i = 0; i < n; i++) {
25 // Water trapped at position i is determined by the minimum of
26 // the maximum heights on both sides minus the current height
27 totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
28 }
29
30 return totalWater;
31 }
32}
33
1class Solution {
2public:
3 int trap(vector<int>& height) {
4 int n = height.size();
5
6 // Arrays to store the maximum height to the left and right of each position
7 vector<int> leftMax(n), rightMax(n);
8
9 // Initialize the first and last elements
10 leftMax[0] = height[0];
11 rightMax[n - 1] = height[n - 1];
12
13 // Build the maximum height arrays
14 // leftMax[i] = maximum height from index 0 to i
15 // rightMax[i] = maximum height from index i to n-1
16 for (int i = 1; i < n; ++i) {
17 leftMax[i] = max(leftMax[i - 1], height[i]);
18 rightMax[n - i - 1] = max(rightMax[n - i], height[n - i - 1]);
19 }
20
21 // Calculate the total trapped water
22 int totalWater = 0;
23 for (int i = 0; i < n; ++i) {
24 // Water level at position i is determined by the minimum of
25 // the maximum heights on both sides
26 // Trapped water = water level - ground height
27 totalWater += min(leftMax[i], rightMax[i]) - height[i];
28 }
29
30 return totalWater;
31 }
32};
33
1/**
2 * Calculates the amount of water that can be trapped after raining
3 * given an elevation map represented by an array of heights.
4 *
5 * @param height - Array representing the elevation map where each element is the height of a bar
6 * @returns The total amount of trapped rainwater
7 */
8function trap(height: number[]): number {
9 const n: number = height.length;
10
11 // Array to store the maximum height to the left of each position (including itself)
12 const leftMax: number[] = new Array<number>(n).fill(height[0]);
13
14 // Array to store the maximum height to the right of each position (including itself)
15 const rightMax: number[] = new Array<number>(n).fill(height[n - 1]);
16
17 // Build the leftMax and rightMax arrays
18 // leftMax[i] = maximum height from index 0 to i
19 // rightMax[i] = maximum height from index i to n-1
20 for (let i: number = 1; i < n; i++) {
21 leftMax[i] = Math.max(leftMax[i - 1], height[i]);
22 rightMax[n - i - 1] = Math.max(rightMax[n - i], height[n - i - 1]);
23 }
24
25 // Calculate the total trapped water
26 let totalWater: number = 0;
27 for (let i: number = 0; i < n; i++) {
28 // Water level at position i is determined by the minimum of
29 // the maximum heights on both sides
30 // Trapped water = water level - ground height
31 totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
32 }
33
34 return totalWater;
35}
36
Time and Space Complexity
The time complexity is O(n)
, where n
is the length of the input array height
. This is because:
- The initialization of
left
andright
arrays takesO(n)
time - The for loop iterates through the array once with
n-1
iterations, performing constant time operations (max
comparisons and assignments) in each iteration, resulting inO(n)
time - The final
sum
operation withzip
iterates through alln
elements once, performing constant time operations (min
comparison and subtraction) for each element, which isO(n)
time - Overall:
O(n) + O(n) + O(n) = O(n)
The space complexity is O(n)
, where n
is the length of the input array height
. This is because:
- Two auxiliary arrays
left
andright
are created, each of sizen
, requiringO(n)
space each - The
zip
operation in the return statement creates an iterator but doesn't create additional arrays - Total auxiliary space:
O(n) + O(n) = O(n)
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Edge Case: Empty or Single Element Array
A frequent oversight is not handling arrays with length 0 or 1, which can cause index out of bounds errors when initializing left_max[0]
or right_max[n-1]
.
Problem Code:
def trap(self, height: List[int]) -> int:
n = len(height)
left_max = [0] * n
right_max = [0] * n
left_max[0] = height[0] # IndexError if height is empty
right_max[n - 1] = height[n - 1]
Solution: Add an early return for arrays that cannot trap water:
def trap(self, height: List[int]) -> int:
n = len(height)
if n <= 2: # Cannot trap water with fewer than 3 bars
return 0
left_max = [0] * n
right_max = [0] * n
# ... rest of the code
2. Incorrect Loop Bounds When Building Arrays
Mixing up the loop boundaries or indices when filling the right_max
array is a common mistake, especially when trying to build both arrays in a single loop.
Problem Code:
# Attempting to fill both arrays in one loop incorrectly
for i in range(1, n):
left_max[i] = max(left_max[i-1], height[i])
right_max[n-i] = max(right_max[n-i+1], height[n-i]) # Off-by-one error
Solution: Keep the loops separate for clarity, or carefully manage indices:
# Separate loops (clearer)
for i in range(1, n):
left_max[i] = max(left_max[i-1], height[i])
for i in range(n-2, -1, -1):
right_max[i] = max(right_max[i+1], height[i])
# Or combined with correct indices
for i in range(1, n):
left_max[i] = max(left_max[i-1], height[i])
right_max[n-i-1] = max(right_max[n-i], height[n-i-1])
3. Memory Optimization Confusion
When attempting the two-pointer optimization to reduce space complexity from O(n) to O(1), developers often incorrectly update the pointers or water calculation logic.
Problem Code:
# Incorrect two-pointer implementation
left, right = 0, n - 1
left_max = right_max = 0
total = 0
while left < right:
if height[left] < height[right]:
total += left_max - height[left] # May add negative water
left_max = max(left_max, height[left])
left += 1
Solution: Update the maximum before calculating water, and ensure non-negative water:
while left < right:
if height[left] < height[right]:
left_max = max(left_max, height[left])
total += max(0, left_max - height[left]) # Or update after max calculation
left += 1
else:
right_max = max(right_max, height[right])
total += max(0, right_max - height[right])
right -= 1
What's the output of running the following function using input 56
?
1KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13 def dfs(path, res):
14 if len(path) == len(digits):
15 res.append(''.join(path))
16 return
17
18 next_number = digits[len(path)]
19 for letter in KEYBOARD[next_number]:
20 path.append(letter)
21 dfs(path, res)
22 path.pop()
23
24 res = []
25 dfs([], res)
26 return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2 '2', "abc".toCharArray(),
3 '3', "def".toCharArray(),
4 '4', "ghi".toCharArray(),
5 '5', "jkl".toCharArray(),
6 '6', "mno".toCharArray(),
7 '7', "pqrs".toCharArray(),
8 '8', "tuv".toCharArray(),
9 '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13 List<String> res = new ArrayList<>();
14 dfs(new StringBuilder(), res, digits.toCharArray());
15 return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19 if (path.length() == digits.length) {
20 res.add(path.toString());
21 return;
22 }
23 char next_digit = digits[path.length()];
24 for (char letter : KEYBOARD.get(next_digit)) {
25 path.append(letter);
26 dfs(path, res, digits);
27 path.deleteCharAt(path.length() - 1);
28 }
29}
30
1const KEYBOARD = {
2 '2': 'abc',
3 '3': 'def',
4 '4': 'ghi',
5 '5': 'jkl',
6 '6': 'mno',
7 '7': 'pqrs',
8 '8': 'tuv',
9 '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13 let res = [];
14 dfs(digits, [], res);
15 return res;
16}
17
18function dfs(digits, path, res) {
19 if (path.length === digits.length) {
20 res.push(path.join(''));
21 return;
22 }
23 let next_number = digits.charAt(path.length);
24 for (let letter of KEYBOARD[next_number]) {
25 path.push(letter);
26 dfs(digits, path, res);
27 path.pop();
28 }
29}
30
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
Want a Structured Path to Master System Design Too? Don’t Miss This!