DSA AnimatorDSA animations
Trapping Rain Water LC #42 Hard Two Pointers
Approach
Two Pointer with Running Max
Track maxLeft and maxRight. Process side with smaller max — water = max − height. O(n) time, O(1) space.
■ Left pointer ■ Right pointer ■ Trapped water ■ Wall
L
—
R
—
maxL
—
maxR
—
water
0
Press Play to start
💧
—
Total trapped water
— —
—
Algorithm
1
L=0, R=n-1, maxL=0, maxR=0, water=0
2
If maxL ≤ maxR: process left side
3
maxL=max(maxL,h[L]); water+=maxL-h[L]; L++
4
Else: maxR=max(maxR,h[R]); water+=maxR-h[R]; R--
Time
O(n)
Space
O(1)
Why It Works

Water at index i = min(maxLeft[i], maxRight[i]) − height[i].

When maxL ≤ maxR, the left pointer's limiting boundary is definitely maxL (right wall is taller), so water = maxL − h[L].

We don't need to know the actual min — the smaller side's max IS the bottleneck.

How to solve Trapping Rain Water

LeetCode 42 · Hard · Arrays · Pattern: Two Pointers

Why the obvious approach is slow

For each bar, you could scan left and right for the tallest walls, which is O(n²). Water above a bar is the smaller of the tallest wall on its left and on its right, minus its own height.

The key idea

Use two pointers, and keep the tallest wall seen from each side. Whichever side has the lower bar is already decided, because the other side is at least as tall. So settle that side: add its water, and move it inward.

Remember

Water at a bar is the smaller of the two tallest walls, minus the bar. With two pointers, the lower side is already decided.

Run the animation above on your own input, or watch the 1:24 video explanation of Trapping Rain Water with a dry run and Java code.

More Arrays problems