LeetCode #42 Hard

Trapping Rain Water

Given bar heights, compute how much rain water the bars trap.

arraytwo-pointers

02

Intuition

Water above any bar is min(tallest-to-left, tallest-to-right) − height. The side with the smaller wall decides the level, so walk two pointers inward from the ends: whichever side is lower is fully determined by its own max — the other side is guaranteed at least as tall.

How to spot this pattern

The two-pointer version comes from noticing that water at a position depends on min(tallest left, tallest right) — and you don't need both numbers, only the smaller one. Whenever a quantity is bounded by a minimum of two running maxima, walk inward from both ends and process whichever side is currently shorter: that side's bound is already known, so it can be settled immediately. The same trick turns container-with-most-water into one pass.

03

Approach

1

Per-bar formula

Column i holds min(maxLeft, maxRight) − h[i] water (never negative). Precomputing both max arrays gives an easy O(n)/O(n) solution.

2

Drop the arrays with two pointers

Keep leftMax and rightMax while pointers close in. If leftMax ≤ rightMax, the left bar's water is leftMax − h[l] — the right side can't be the binding wall. Move that pointer.

3

Sum as you go

Each step settles exactly one column. O(n) time, O(1) space.

04

Solution & live demo

▶1class Solution:
▶2    def trap(self, height):
▶3        l, r = 0, len(height) - 1
▶4        left_max = right_max = water = 0
▶5        while l < r:
▶6            if height[l] <= height[r]:
▶7                left_max = max(left_max, height[l])
▶8                water += left_max - height[l]
▶9                l += 1
▶10            else:
▶11                right_max = max(right_max, height[r])
▶12                water += right_max - height[r]
▶13                r -= 1
▶14        return water

05

Common pitfalls

Comparing the running maxima instead of the current bars

✗ Wrong

if left_max <= right_max:
    ...
    l += 1

✓ Right

if height[l] <= height[r]:
    ...
    l += 1

Both maxima start at 0 and update lazily, so the comparison can pick a side whose true bound isn't settled yet and bank water that a taller bar later invalidates. Comparing the actual bars is what proves the shorter side is limited by its own max — that's the invariant the whole method rests on.

Adding water before updating the wall

✗ Wrong

water += left_max - height[l]
left_max = max(left_max, height[l])

✓ Right

left_max = max(left_max, height[l])
water += left_max - height[l]

If the current bar is the tallest so far it should hold no water, but against the stale left_max the subtraction goes negative and quietly removes water banked earlier. Raising the wall first makes the term exactly zero for a new peak.

06

Edge cases

Monotone slope, e.g. [1,2,3]

Smaller wall is always the current bar itself — every contribution is 0.

Fewer than 3 bars

No basin can form; loop yields 0.

07

Complexity

Time

O(n)

Space

O(1)

Each pointer moves n times total.