Trapping Rain Water
Work out how much rain collects between bars of different heights. A classic test of two pointers and reasoning about left and right maximums. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given an array height of non-negative integers. Each value is the height of a bar of width 1, and the bars stand side by side. After it rains, water collects in the dips between bars.
Return the total amount of water trapped. Water can't be held at either end of the array, since there is nothing beyond the first and last bar to contain it.
Example 1
- Input
- height = [3, 0, 2, 0, 4]
- Output
- 7
The water level across the middle is 3, set by the shorter outer wall. That holds 3 + 1 + 3 units above the three inner bars.
Example 2
- Input
- height = [1, 2, 3, 2, 1]
- Output
- 0
Every bar slopes away from the peak, so water runs off.
Example 3
- Input
- height = [5, 2, 1, 2, 1, 5]
- Output
- 14
Constraints
- 1 ≤ height.length ≤ 2 × 10⁴
- 0 ≤ height[i] ≤ 10⁵
Practice
Runs 13 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Trapping Rain Water in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Trapping Rain Water
Pattern: Two pointers with running maximums
Don't try to find the "pools" directly. Look at one column at a time instead. The water above column i rises until it would spill over the shorter of two walls: the tallest bar anywhere to its left and the tallest bar anywhere to its right. So:
water[i] = min(maxLeft[i], maxRight[i]) - height[i]
That formula alone gives an O(n) solution with two precomputed arrays. The two-pointer trick removes the arrays. Put a pointer at each end and track the tallest bar seen from each side. Whichever side has the smaller running maximum is the limiting side: the true maximum on the other side is at least as tall as what you've already seen there, so the shorter side's maximum is the water level. Settle that column, move that pointer inward, and repeat.
Approach 1: Brute force per column
For every column, scan left for the tallest bar and scan right for the tallest bar, then add min(left, right) - height[i]. Direct translation of the formula, but each column rescans the array.
Time O(n²) · Space O(1)
Approach 2: Precomputed prefix and suffix maximums
Build maxLeft in one pass left to right and maxRight in one pass right to left, then sum min(maxLeft[i], maxRight[i]) - height[i] in a third pass. Linear time, but it uses two extra arrays.
Time O(n) · Space O(n)
Approach 3: Two pointers
Start with left = 0, right = n - 1, and leftMax = rightMax = 0. While left < right:
- If
height[left] < height[right]: updateleftMaxwithheight[left], addleftMax - height[left], and moveleftright. - Otherwise do the same on the right side and move
rightleft.
Comparing the current bars is enough: if height[left] < height[right], there is a bar on the right at least as tall as anything that could limit the left side, so leftMax is the water level for column left.
Time O(n) · Space O(1)
| Approach | Time | Space |
|---|---|---|
| Brute force per column | O(n²) | O(1) |
| Precomputed prefix and suffix maximums | O(n) | O(n) |
| Two pointers | O(n) | O(1) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Trapping Rain Water solution in Python
def trap(height: list[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
if height[left] < height[right]:
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return waterTrapping Rain Water solution in JavaScript
function trap(height) {
let left = 0;
let right = height.length - 1;
let leftMax = 0;
let rightMax = 0;
let 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;
}Common mistakes
- Using the taller of the two walls instead of the shorter. Water spills over the lower side.
- Trying to find pools by scanning for "valleys", which breaks on nested shapes like `[5, 2, 1, 2, 1, 5]` where an inner dip sits inside a larger basin.
- Moving the pointer on the taller side, which settles a column before its real limit is known.
- Adding water at the first or last column, or forgetting that arrays with fewer than three bars hold nothing.
What interviewers look for
Lead with the per-column formula, min(maxLeft, maxRight) - height. It is the real insight, and stating it shows you've reduced a 2D picture to a 1D calculation. Interviewers are usually happy to see the prefix/suffix array version first and then the space optimization.
When you present the two-pointer version, spend a sentence on why it's safe to settle the shorter side. That justification is what separates a memorized answer from an understood one.
Follow-up questions
Can you solve it with a stack instead?
Yes. Keep a stack of indices with decreasing heights. When a taller bar arrives, pop the bottom of a dip, and fill the layer between the new top of the stack and the current bar: width is the distance between them minus one, height is the shorter of the two walls minus the popped bar. This adds water layer by layer in O(n) time and O(n) space.
What if the bars form a 2D grid of heights instead of a single row?
Use a min-heap seeded with every border cell. Repeatedly pop the lowest cell; for each unvisited neighbor, water fills it up to the popped height if it is lower, and the neighbor is pushed with height `max(its height, popped height)`. That runs in O(m · n · log(m · n)).
What if heights stream in and you can only make one pass?
Use the stack approach, which only looks backward: each new bar settles any water it closes off on its left. Water to the right of the tallest bar so far stays unresolved until a taller bar arrives, which the stack holds.
Companies that ask Trapping Rain Water
Trapping Rain Water is tagged by 161 companies in our interview dataset. The score shows how often it comes up at each company.
- Goldman Sachs100%
- Albertsons100%
- Verizon100%
- Terumo100%
- Fdm Group100%
- Zenefits100%
- Cadence Design Systems100%
- Thousandeyes100%
- Twitter97%
- Walmart Labs96.9%
- Ola90.7%
- Samsung90.3%
- Sabre90%
- Weedmaps90%
- Snowflake89.9%
- Wisetech Global89%
- Urban Company88.8%
- Amazon88%
- Rakuten88%
- Servicenow87.9%
- Hive87.4%
- Wixcom87.3%
- Zoho86.6%
- Wizeline84%
and 137 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required