vizlearn

Trapping rain water

Interview QuestionsBy Updated

Water above one bar is min(tallest left, tallest right) − its own height. The two-pointer version exploits one fact: whichever side is shorter is the binding constraint, so that side's water can be settled immediately. One pass, O(1) space.

Overview

The per-bar formula

Water sits above a bar up to the level of the lower of the two walls containing it: min(max to the left, max to the right) − height, or zero if that is negative.

The direct implementation precomputes both arrays of running maxima and then sums. That is O(n) time and O(n) space, perfectly correct, and the right first answer. The two-pointer version removes the arrays.

Lists & arraysCoding problemHard

Step through it

What to watch

  • Only the shorter side is advanced, and only that side's water is settled.
  • The running maxima are two integers, not two arrays.
  • Each bar is visited exactly once.

Say this out loud

"Per bar it's min of the max to the left and the max to the right, minus its height. Two pointers from both ends: always move the shorter side, because that side's maximum is what limits it. O(n) time, O(1) space."

Trapping rain water

Given bar heights, how much water is trapped between them?

Why moving the shorter side is safe

Suppose height[lo] < height[hi]. Then whatever the maxima turn out to be, the left side's is the smaller of the two — because there is already a bar at least as tall as height[hi] on the right. So the water above lo is decided by left_max alone and can be settled now, without knowing anything more about the right.

That is the whole argument, and it is worth stating explicitly. Candidates who write this from memory usually cannot say why moving the shorter side is the correct choice.

The stack alternative

A monotonic decreasing stack also solves it in O(n), filling water horizontally layer by layer rather than column by column. It is harder to get right under pressure and worth naming as an alternative.

The same "maximum to the left and right of each element" shape appears in largest-rectangle-in-a-histogram and stock-span, so recognising it is worth more than memorising this one solution.

Run it in Python

The two-pointer sweep against the precomputed-arrays version and a brute force, with the extra memory each one uses printed — all three agreeing on every test.

rain_water.pyPython 3
Output
How the code works
  1. if heights[lo] < heights[hi]:The decision the whole approach rests on. The shorter side is necessarily the smaller of the two maxima, so its water is already determined.
  2. total += left_max - heights[lo]Settled immediately, with no knowledge of the right side. That is only valid because of the comparison above — be ready to say why.
  3. left_max = max(left_max, heights[lo])Two integers replace the two arrays of the previous version. The algorithm is the same; only the bookkeeping shrank.
  4. while lo < hiStrictly less than. The two pointers meeting means every bar has been settled exactly once.
Change one thing
  • Feed it a strictly increasing list. The answer is zero — there is no right wall to hold anything.
  • Print lo, hi and both maxima each iteration and check that the shorter side is always the one that moves.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. The water above a single bar equals:
  2. Why is it safe to settle the shorter side's water immediately?
  3. The two-pointer version improves on the precomputed-arrays version in:





 Cheat sheet
Trapping rain water
Water above one bar is min(tallest left, tallest right) − its own height. The two-pointer version exploits one fact: whichever side is shorter is the binding constraint, so that side's water can be settled immediately. One pass, O(1) space.
INTERVIEW · vizlearn.in/interview/trapping-rain-water.html
More in Interview
InterviewSort an array of 0s, 1s and 2sInterview3SumInterviewSearch in a rotated sorted arrayInterviewSliding window maximum
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact