The Water Gauge

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4

Problem

A terrain heightmap is stored as a list of non-negative bar heights. After heavy rain, water collects in the dips between taller bars; return the total units of water the profile traps.

Elevation bars trap water in the dips. Total the volume.

Example

Input:

heights = [0,1,0,2,1,0,1,3,2,1,2,1]

Output:

6

Worked solution and explanation

What this really is

Strip the rain metaphor and this is a bounded-minimum problem: the water standing over bar i is min(tallest bar to its left, tallest bar to its right) - heights[i], and never less than zero. Everyone lands the min part eventually. The trap is the bookkeeping. Candidates reach for a single running maximum and discover it only ever sees ONE wall, so they either rescan both sides at every bar (O(n^2)) or, worse, take the max of the two walls instead of the min. Take the max and you claim water piled higher than the shorter wall can hold: physically impossible volumes. Forget to clamp at zero and a tall bar sitting in a trough contributes negative water and drags your total down.

Getting to one pass, O(1) space

Step 1: Anchor two pointers at the ends

Put left at index 0 and right at the last bar, and remember the tallest bar seen from each end so far in left_max and right_max. These two scalars are your only known walls.

Step 2: Advance the side with the shorter wall

Move whichever pointer sits behind the shorter wall. If left_max <= right_max, the left wall is binding, so advance left; otherwise advance right. Because the shorter wall caps the water, you can commit that side without ever knowing the taller wall's exact height.

Step 3: Commit water as you go

After each move, refresh that side's running max, then add running_max - heights[pointer] to the total. It is always non-negative because the running max already includes the current bar.

The solution

Two converging pointers, O(1) space
def trap_rainwater(heights: list[int]) -> int:
    if len(heights) < 3:
        return 0
    left, right = 0, len(heights) - 1
    left_max, right_max = heights[left], heights[right]
    total = 0
    while left < right:
        if left_max <= right_max:
            left += 1
            left_max = max(left_max, heights[left])
            total += left_max - heights[left]
        else:
            right -= 1
            right_max = max(right_max, heights[right])
            total += right_max - heights[right]
    return total
Prefix/suffix max arrays
Two passes build left_max[i] and right_max[i], a third sums min(...) - h[i]. Dead clear, three linear scans, but O(n) extra space for the two arrays. A perfectly good first answer to say out loud, and it embodies the same min-of-two-walls insight.
Two converging pointers
Keep only two scalars for the running maxima and walk inward from both ends. Same O(n) time, but O(1) space, because the shorter wall is always the binding one. This is the version to land.

Common follow-up questions