← DSA Atlas
Dedicated problem page · #42

Trapping Rain Water

HardTwo PointersConverging pointers tracking left/right maximaTwo pointers
Solve on LeetCode ↗
42
HardTwo PointersTwo pointersConverging pointers tracking left/right maxima

Trapping Rain Water

Given an array height representing an elevation map where each bar has width 1, compute how many units of water can be trapped between the bars after it rains.

Open official problem prompt ↗
In plain English

Total the rainwater that settles in the valleys of a bar-chart elevation map.

Picture it like this

Two flood inspectors walk toward each other from opposite banks; the one on the lower embankment knows the water level over their spot is set by their own bank, so they measure and step inward.

Example
Input
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output
6
Why
Water pools in the dips: summing trapped units across all positions gives 6 total.
Constraints
n == height.length1 <= n <= 2 * 10^40 <= height[i] <= 10^5
Pattern lesson

See the pattern, then code

Converging pointers tracking left/right maxima
Recognition clue

Water at a position depends on the min of the tallest bar to its left and right; computing those bounds while walking inward from both ends is the two-pointer signal.

↗
Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. Water over a bar equals min(max-left, max-right) minus its own height. Whichever side currently has the smaller running max is the binding side, so you can safely finalize that position and move that pointer inward.

New words, made simpleKnow these before the algorithm
left_max / right_max
Tallest bar seen so far from the left end and the right end respectively.
Binding side
The side whose running max is smaller and therefore caps the water level at the current position.
Trapped units
For a position, min(left_max, right_max) minus its own height, floored at zero.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Per-position scan

Quadratic and too slow for n up to 20000.

For each bar, scan left and right to find the bounding maxima.

Time O(n^2)Space O(1)
Prefix/suffix max arrays

Linear time but uses extra arrays.

Precompute left_max and right_max arrays, then sum the water in one pass.

Time O(n)Space O(n)
Best choiceTwo pointers

Linear time and constant space; the optimal solution.

Walk inward from both ends, always advancing the smaller-max side and accumulating water.

Time O(n)Space O(1)
The rule we keep true

Invariant

When left_max < right_max, the smaller of the two global maxima at the left pointer is exactly left_max, so the water above height[left] is fully determined and equals left_max - height[left].

Why this is correct

Reasoning

Water level at a spot is capped by the shorter of the two surrounding maxima. If the left running max is smaller than the right running max, there is guaranteed to be a bar at least right_max tall somewhere to the right, so left_max already fixes the level; the same argument mirrors on the other side, letting each position be settled exactly once.

The algorithm in three movesSay these aloud before coding
1Set left/right pointers at the ends and track left_max and right_max

left_max grows 0->1->2, right_max grows from the right

2While pointers have not crossed, work on the side with the smaller running max

at each step add min-side max minus height

3Advance that pointer, update its running max, and add running_max minus current height to the total

total water = 6

4Return the accumulated water

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
11
02
23
14
05
16
37
28
19
210
111
1 · Readleft=0(0), right=11(1)
2 · AskWhich side binds?
3 · Update stateleft_max=0, right_max=1
4 · Resultleft_max smaller; move left.
Key takeaway

The tall bars at indices 3 and 7 bound the basins where the 6 units of water collect.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Set up ends

    Initialize pointers and running maxima at the two boundaries.

  2. 2
    Lines 8-12Left side binds

    When left_max is smaller, advance left, refresh left_max, and bank left_max - height[left].

  3. 3
    Lines 13-16Right side binds

    Otherwise advance right symmetrically, accumulating right_max - height[right].

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Fewer than 3 bars trap no water
  • Monotonically increasing or decreasing heights trap zero
  • Flat equal heights trap zero
  • A single deep valley between two tall walls traps the full basin
!

Common beginner mistakes

  • Comparing height[left] vs height[right] instead of left_max vs right_max, which breaks the correctness argument
  • Updating the running max after adding water, producing negative contributions
  • Off-by-one so a boundary bar is double counted
Check your understanding

Why is it safe to finalize the left position when left_max < right_max even though we have not scanned everything to the right?

More in Two Pointers

#153SumSorted two-pointer scan around a fixed anchor#11Container With Most WaterConverging pointers on a width-vs-height tradeoff#184SumTwo fixed anchors plus a sorted two-pointer inner scan#26Remove Duplicates from Sorted ArraySlow/fast in-place overwrite#31Next PermutationFind pivot, swap successor, reverse suffix#75Sort ColorsDutch National Flag partition