Trapping Rain Water — LeetCode 42
The Trapping Rain Water problem is a classic array problem that teaches an important two-pointer technique.
Problem
You are given an array where each element represents the height of a bar. Each bar has width 1.
After it rains, water can be trapped between these bars.
For example:
height = [0,1,0,2,1,0,1,3,2,1,2,1]
The total amount of trapped water is 6.
The Basic Idea
For any position i, the amount of water trapped above it depends on the tallest bar on its left and the tallest bar on its right.
The water level is determined by the shorter of these two boundaries.
So:
water[i] = min(leftMax, rightMax) - height[i]
For example, if:
leftMax = 4
rightMax = 5
height[i] = 2
rightMax = 5
height[i] = 2
Then:
water = min(4,5) - 2
= 2
= 2
Brute Force Approach
For every position, we can find:
- The maximum height on the left.
- The maximum height on the right.
- Calculate the water trapped at that position.
This works, but finding the maximum on both sides for every position makes the time complexity O(n²).
Using Extra Arrays
We can improve this by precomputing two arrays:
leftMax[i] = maximum height from the beginning up to i
rightMax[i] = maximum height from i up to the end
Then:
water[i] = min(leftMax[i], rightMax[i]) - height[i]
This gives O(n) time, but requires O(n) extra space.
The Two-Pointer Approach
We can do even better.
Instead of storing the maximum values for every position, we use two pointers:
left starts at the beginning.
right starts at the end.
right starts at the end.
We also maintain:
leftMax = maximum height seen from the left
rightMax = maximum height seen from the right
The important observation is:
If height[left] is smaller than height[right], we process the left side.
If height[right] is smaller, we process the right side.
Why?
Because the smaller side is the limiting boundary.
Suppose:
height[left] < height[right]
We already know that there is a sufficiently tall boundary on the right. Therefore, for the current left position, the left boundary is the one that determines how much water can be trapped.
So we can safely calculate:
water += leftMax - height[left]
Similarly, when the right side is smaller:
water += rightMax - height[right]
C++ Solution
class Solution {
public:
int trap(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
public:
int trap(vector<int>& height) {
int left = 0;
int right = height.size() - 1;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int leftMax = 0;
int rightMax = 0;
int water = 0;
while (left <= right) {
if (height[left] <= height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
}
else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}};
Complexity
Time Complexity: O(n) ( Each pointer moves through the array only once.)
Space Complexity: O(1)
We only use a few variables regardless of the size of the input.
The Key Insight
The entire problem comes down to one equation:
water[i] = min(leftMax, rightMax) - height[i]
And the two-pointer optimization comes from realizing:
The smaller boundary is the limiting boundary.
Once you understand that, the two-pointer solution becomes much easier to derive instead of simply memorizing it.
Enjoyed reading this content? Let the author know!
Your likes, comments, shares, and saves help creators reach more builders.
Loading recommendations
Loading article