Trapping Rain Water
Given n non-negative integers that describe an elevation map, where each bar has width 1, compute how much water is trapped after it rains. This is LeetCode 42.
Example 1
Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]Output: 6
Example 2
Output: 9
How to Think About It
Step 1: Water above one bar
Look at a single bar i
water[i] = min(maxLeft[i], maxRight[i]) - height[i]
Here maxLeft[i]maxRight[i]i
Step 2: A version with extra arrays
One pass from the left fills maxLeftmaxRight
Step 3: Only the smaller side matters
Keep leftrightleftMaxrightMaxheight[left] < height[right]
- There is a bar on the right of
, namelyleft , that is taller thanheight[right] .height[left] - So whatever the true
is, the water atmaxRight[left] is limited by the left side only: it isleft .leftMax - height[left]
Add that, and move left
Step 4: Finish when the pointers meet
Each bar is settled exactly once, by whichever pointer reaches it.
Walkthrough
height = [4, 2, 0, 3, 2, 5]
| Bar settled | Height | leftMax | Water added | Total |
|---|---|---|---|---|
| 0 | 4 | 4 | 0 | 0 |
| 1 | 2 | 4 | 2 | 2 |
| 2 | 0 | 4 | 4 | 6 |
| 3 | 3 | 4 | 1 | 7 |
| 4 | 2 | 4 | 2 | 9 |
The pointers meet at bar 5, and the total is 9.
Java Solution
The comparison between the two current bars decides which side is safe to settle.
public class TrappingRainWater {
public static int trap(int[] height) {
int left = 0;
int right = height.length - 1;
int leftMax = 0; // tallest bar seen from the left so far
int rightMax = 0; // tallest bar seen from the right so far
int water = 0;
while (left < right) {
if (height[left] < height[right]) {
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left]; // right side is sure to be at least as tall
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right]; // left side is sure to be at least as tall
right--;
}
}
return water;
}
public static void main(String[] args) {
System.out.println(trap(new int[] {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})); // 6
System.out.println(trap(new int[] {4, 2, 0, 3, 2, 5})); // 9
}
}
The original implementation,
Complexity
- Time: O(n): each bar is settled once.
- Space: O(1), compared with O(n) for the version with two arrays.
A monotonic stack solves the same problem by filling water layer by layer: see