Trapping Rain Water

Given height, an array where height[i] is the height of a bar of width 1, compute how much rain water can be trapped between the bars after it rains.

Hints

· Stuck? Reveal one nudge at a time.

How much water sits above one bar? It's bounded by the shorter of its two side maxima.

Water above bar i = min(leftMax, rightMax) - height[i].

Two pointers with running maxima: always advance the shorter side.

Common doubts

Water can only rise to the lower of the two enclosing walls; a taller wall on one side is irrelevant if the other side is shorter.

If height[l] < height[r], the right wall is at least as tall, so min(leftMax, rightMax) for bar l equals leftMax — which you already know. Moving l processes it exactly.

It computes the same min(leftMax, rightMax) on the fly with two running variables, dropping the O(n) space for the prefix/suffix max arrays.

Interview follow-ups

· What an interviewer asks next.

Keep a decreasing stack of bar indices; when a taller bar arrives, pop and add water for the bounded valley — an O(n) alternative that computes water in horizontal layers.

It uses a min-heap over the boundary cells, always processing the lowest boundary — a priority-queue generalization of the shorter-wall idea.

Fun facts

Trapping Rain Water is a rite-of-passage two-pointer problem, prized for how the shorter-wall insight collapses O(n) space to O(1).
The same 'shorter side binds, advance it' logic drives Container With Most Water.

Asked at

AmazonGoogleMetaMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
The dips between the bars trap 6 units of water in total.

Example 2

Input: height = [4,2,0,3,2,5]
Output: 9
Water pools between the tall end bars for a total of 9 units.

Constraints

- 1 <= height.length <= 2 * 10^4 - 0 <= height[i] <= 10^5

Water sitting above bar i is bounded by the shorter of the tallest bar to its left and the tallest bar to its right, minus its own height: min(leftMax, rightMax) - height[i]. Computing those maxima naively is O(n) per bar; a two-pointer sweep gets the whole answer in O(n) time and O(1) space by always advancing the shorter side.

Prerequisites

Before you start

· Concepts used directly in the solution.

Bounded-by-shorter-wall. Water above a bar is capped by the smaller of its two surrounding maxima.

Two pointers. Advancing from both ends, moving whichever side is provably safe.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The model

“Do the bars have width?”

Yes — each has width 1, so trapped water above bar i is a column of height min(leftMax, rightMax) - height[i].

“Can water be negative?”

No — if a bar is at least as tall as its bounding walls, it traps 0.

The ideal opening — say it like this

The water on top of each bar is min(tallest-to-the-left, tallest-to-the-right) minus its own height.

I use two pointers and track the running max on each side.

Whichever side is shorter is the binding wall, so I add its water and move it inward — O(1) space.

Understand the problem

Worked example — height = [0,1,0,2,1,0,1,3,2,1,2,1]

water traps in the dips between taller bars, totaling 6 units
answer: 6

Key observations

1Aha

Water is bounded by the shorter wall

Bar i holds min(leftMax, rightMax) - height[i] of water — the taller wall doesn't matter, the shorter one caps the level.

2Aha

Advance the shorter side safely

If height[l] < height[r], the left wall is binding for bar l (the right can only be taller), so leftMax - height[l] is exact. Move l. Symmetric for the right.

3Aha

O(1) space

Running leftMax/rightMax replace the two prefix/suffix-max arrays, so the sweep needs only a few variables.

Brute force vs optimal

	Scan both sides per bar	Two pointers
Idea	For each bar, find left and right maxima by scanning	Advance the shorter side with running maxima
Time	O(n^2)	O(n)
Space	O(1)	O(1)

(A middle-ground stores prefix/suffix maxima in O(n) space for O(n) time; the two-pointer version removes even that.) Full code is in the Approaches selector below.

Summary

Key takeaway

Water above each bar is min(leftMax, rightMax) - height[i]. Two pointers with running maxima always advance the shorter side — whose max is the exact binding wall — accumulating the trapped water in O(n) time and O(1) space.

l, r = 0, n-1; leftMax = rightMax = water = 0
while l < r:
    if height[l] < height[r]: leftMax = max(leftMax, height[l]); water += leftMax - height[l]; l += 1
    else:                     rightMax = max(rightMax, height[r]); water += rightMax - height[r]; r -= 1
return water