Trapping Rain Water
Hard Opposite ends with max heights
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Bars of given heights stand side by side. Return how much rain water is trapped between them.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: how much rain sits between the bars?
Why this works: water above a bar = min(tallest on left, tallest on right) - bar. With two pointers, the side with the smaller max is already decided, so process that side.
Example: [4, 2, 0, 3, 2, 5]
leftMax 4 < rightMax 5 → water at 2: 2, at 0: 4, at 3: 1, at 2: 2total 9
✦Hints open one at a time
↗Approach
Keep leftMax and rightMax. If leftMax < rightMax, the water at l depends only on leftMax (the right side is guaranteed to be at least as tall), so add leftMax - height[l] and move l. Otherwise do the same on the right.
</>Solution (Java)
class Solution {
public int trap(int[] height) {
int l = 0, r = height.length - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (l < r) {
leftMax = Math.max(leftMax, height[l]);
rightMax = Math.max(rightMax, height[r]);
if (leftMax < rightMax) {
water += leftMax - height[l]; // left side decides
l++;
} else {
water += rightMax - height[r];
r--;
}
}
return water;
}
}!Common mistake
For each bar, scanning left and right for the maximum — O(n²).
- Time: O(n).
- Space: O(1).
