Trapping Rain Water
Walkthrough video coming soon
The full explanation is written out below — the problem, the intuition, the approach, and the solution code.
The problem
Given `n` non-negative integers representing an elevation map where the width of each bar is 1, compute how much rain water it can trap after raining.
Constraints & assumptions
- n == height.length
- 1 ≤ n ≤ 2·10⁴
- 0 ≤ height[i] ≤ 10⁵
In plain English
Picture a city skyline of buildings of different heights, and then it rains. Water pools in the gaps between buildings. How much collects on top of any one spot? It's capped by the shorter of the two tallest walls on its left and right — water spills over the lower side.
So for each position, the trapped water is min(tallest-on-left, tallest-on-right) − its own height. The whole problem is just adding that up across every position. The clever part is computing those left/right maxima efficiently.
What you need to know
The programming concepts this problem is built on:
How to approach it
- 1For each bar, the water it holds is min(maxLeft, maxRight) − height, never negative.
- 2One way: precompute the tallest wall to the left and to the right of every bar in two arrays.
- 3A slicker way: two pointers move inward, always advancing the side with the smaller wall.
- 4That side's running maximum fully determines its water, so we add it and step inward.
The solutions
2 waysThis one can be solved more than one way. Switch between the methods to compare — each summary explains how it differs.
Converge from both ends in O(1) extra space.
We keep pointers at both ends and always process the side with the smaller height. Because that side's wall is the limiting factor, its running max alone decides the water there — so we never need to store the maxima. Optimal in both time and space.
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] < height[right]) {
leftMax = Math.max(leftMax, height[left]);
water += leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
water += rightMax - height[right];
right--;
}
}
return water;
}
}