Coding · Two pointers
Trapping Rain Water
- Reported in several places
- Hard
- 2 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
Each element of an array is the height of a unit-wide bar, and the bars stand side by side. After rain, water collects in the gaps and cannot spill over a taller wall or past either end of the row; return how many units of water the whole row holds. For heights [3, 1, 0, 2, 0, 5, 1, 4] the answer is 12. The array has up to 100,000 bars, with heights from 0 to 100,000.
Restated in our own words, not a quote from Amazon or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: are the heights non-negative integers, as the problem suggests? Is every bar exactly one unit wide? Does water at the two ends spill away, so the first and last bar can never hold any? What should I return for an empty row, a single bar, or two bars? May I use extra arrays, or is constant extra memory expected?
I would assume non-negative integer heights, unit widths, water spilling off both ends, and 0 for any row of fewer than three bars. I will aim for one pass over the input and then see how little memory I can use.
Brute force
Say the obvious answer and why it is too slow.
Look at one position at a time. The water standing above bar i reaches the lower of two walls: the tallest bar at or left of i and the tallest bar at or right of i. So for every i, scan left for the maximum, scan right for the maximum, and add the lower of the two minus the height of bar i.
That is correct, and it is O(n²): each position triggers two scans that together cover the whole row. With 100,000 bars that is about ten billion comparisons, which will not finish in time. You can store the prefix maximums and suffix maximums in two arrays to get O(n) time, but then you spend O(n) memory on tables that we can avoid.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n)
- Space
- O(1) extra
The formula for one position is min(tallest to the left, tallest to the right) - height. Notice that only the smaller of the two maximums matters. So we do not need both exact values at every position, only to know which side is the smaller one.
Put a pointer at each end and keep leftMax and rightMax for the bars already passed on each side. Compare the two bars under the pointers and handle the shorter one. Suppose the left bar is shorter. Every bar we have already passed on the left was shorter than some bar on the right at that moment, and that taller bar is still somewhere to the right of the left pointer. So the true right-hand wall for this position is at least as high as leftMax, and the left side is the limiting wall. Water here is exactly leftMax - height, with no need to know the real right maximum. Then we move the left pointer in. The case where the right bar is shorter is the mirror image.
Each step settles one position for good and moves one pointer, so the pointers meet after n - 1 steps. Update the running maximum before computing the water, so the amount is never negative.
The pattern is two pointers moving inward, deciding by the smaller side. Out loud: "the lower wall decides, so I always advance from the lower side, where I am certain of the limiting wall."
Walk it through
A dry run on the example, step by step.
| Pointers | Compare | Side moved | Maxes (L, R) | Water total |
|---|---|---|---|---|
| left 0, right 7 | 3 < 4 | left | 3, 0 | 0 |
| left 1, right 7 | 1 < 4 | left | 3, 0 | 2 |
| left 2, right 7 | 0 < 4 | left | 3, 0 | 5 |
| left 3, right 7 | 2 < 4 | left | 3, 0 | 6 |
| left 4, right 7 | 0 < 4 | left | 3, 0 | 9 |
| left 5, right 7 | 5 >= 4 | right | 3, 4 | 9 |
| left 5, right 6 | 5 >= 1 | right | 3, 4 | 12 |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Use the row [3, 1, 0, 2, 0, 5, 1, 4]. The right pointer starts on the 4. The left bar 3 is lower than 4, so we set leftMax to 3, add nothing, and move right. The next four left bars (1, 0, 2, 0) are all lower than 4 and lower than the leftMax of 3, so they hold 2, 3, 1 and 3 units: the running total reaches 9.
Now the left pointer is on the 5, which is not lower than the 4 on the right, so we switch sides. The right wall is the shorter one: rightMax becomes 4, and the bar of height 4 holds nothing. Then the right pointer moves to the 1, which holds 4 - 1 = 3 units, and the total is 12. The pointers have met. Check the water column row by row in the table.
The code
Runnable JavaScript, checked against test cases.
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;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
An empty row, one bar or two bars: the loop condition left < right either fails at once or the two bars hold nothing, so the answer is 0. A row that only rises or only falls never has a smaller maximum behind it, so every step adds 0. A flat row adds 0 each time.
Ties between the two pointer bars go to the right side; either choice is correct because the two maximums are then both limited by that same height. Leading and trailing zeros are fine because the maximum starts at 0 and zero minus zero adds nothing. The total can reach about ten billion, which a JavaScript number holds exactly, so no overflow handling is needed.
Follow-ups to expect
Where the interviewer pushes next.
- How would you solve it with a monotonic stack, and when is that version more natural?
- How would you compute the water for a two-dimensional grid of heights?
- Can you return the water level at every position instead of the total?
- What changes if bars have different widths?
- How does the prefix and suffix maximum version compare in memory and in readability?
Where candidates slip
The mistakes this problem punishes.
The classic mistake is using the global maximum as one wall, which ignores that a closer, lower wall limits the water. Another is computing the water before updating the running maximum, which produces negative amounts on a new peak.
Candidates also advance the wrong pointer: with the bar comparison used here, the pointer on the lower bar must move, and moving the taller side's pointer settles a position whose limiting wall is not yet known. And many jump straight to the two-pointer code without being able to explain why the other side's exact maximum is not needed, which is the part worth being ready to explain.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.