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.

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

python

▶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

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.

06

Complexity

Time

O(n)

Space

O(1)

Each pointer moves n times total.