Two Pointer Pattern

Trapping Rain Water

Given n non-negative integers where height[i] is the height of a bar of width 1 at position i, imagine it rains until no more water can settle. Return the total units of water trapped in the dips between the bars. Water sits above a bar only if there are taller bars on both sides to hold it in; water at the outer edges spills away. Return a single number (0 if nothing is trapped).

CONSTRAINTS

n == height.length
1 <= n <= 2 × 10⁴
0 <= height[i] <= 10⁵

EXAMPLE 1

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Water settles in each dip up to the shorter of the tallest walls on its two sides; summed across all bars it comes to 6 units.

EXAMPLE 2

Input: height = [4,2,0,3,2,5]

Output: 9

The valley between the 4 on the left and the 5 on the right holds water up to height 4 where the floor allows, totaling 9 units.

EXAMPLE 3

Input: height = [3,2,1]

Output: 0

The bars only descend, so there is never a taller wall on the right to hold water in. Nothing is trapped.

Can water sit at the two outer edges?

No. The outermost bars have no wall beyond them, so any water there just spills off the ends.

What does the height of a bar represent?

Each bar has width 1 and the given height; water fills the empty space above bars that sit lower than the walls on both sides.

Does the input need to be sorted?

No. This works on the raw elevation map — the discard rule comes from the shorter boundary wall, not from any ordering.

What should a strictly increasing or decreasing array return?

Zero. With bars only going up (or only down), one side never has a taller wall to trap water against.

Picture a row of bars of different heights, then rain. Water pools in the dips. The one fact everything rests on: the water sitting on top of a single bar rises only as high as the shorter of two walls — the tallest bar somewhere to its left, and the tallest bar somewhere to its right. Call those leftMax and rightMax. The water above bar i is min(leftMax, rightMax) - height[i] (and zero if that comes out negative). Add it up over every bar and you have the answer. The whole challenge is computing those two "tallest wall on each side" values without wasting time or memory.

The blunt way, and a faster-but-heavier fix

The literal approach: for each bar, scan all the way left for its tallest left wall and all the way right for its tallest right wall, then add its water. Correct, but each bar triggers two full scans — O(N²).

python

total = 0
for i in range(len(height)):
    left_max = max(height[:i+1])       # tallest wall at or left of i
    right_max = max(height[i:])        # tallest wall at or right of i
    total += min(left_max, right_max) - height[i]
return total

An easy speedup is to precompute those walls once. Sweep left to right filling a leftMax array, sweep right to left filling a rightMax array, then read both off for each bar. That is O(N) time — but it spends O(N) extra memory on the two arrays. Can we get the walls without storing them?

Two ends, each carrying the tallest wall it has seen

Yes — with the converging walk, plus one running number on each side. Put left at the first bar and right at the last. As left moves in it remembers leftMax, the tallest bar it has passed so far; as right moves in it remembers rightMax. At each step, advance the pointer sitting on the shorter current bar, and bank that bar's water using the running max on its own side.

python

left, right = 0, len(height) - 1
left_max, right_max, water = 0, 0, 0
while left < right:
    if height[left] < height[right]:
        left_max = max(left_max, height[left])
        water += left_max - height[left]   # water on the left bar
        left += 1
    else:
        right_max = max(right_max, height[right])
        water += right_max - height[right]  # water on the right bar
        right -= 1
return water

Why the shorter side can be settled with only its own running max

This is the subtle step, so let's argue it honestly. Suppose height[left] < height[right], and we're about to settle the left bar using only left_max — ignoring whatever the true tallest wall on its right might be. Is that valid? The water on the left bar is min(left_max, trueRightMax) - height[left]. We're claiming it equals left_max - height[left], which needs left_max <= trueRightMax. Two things guarantee it. First, trueRightMax is at least height[right], since right is one of the bars on that side. Second — the important part — every time left advanced past a tall bar in the past, it did so only because the bar at right was even taller at that moment (that is the exact condition for moving left), and right_max only grows as right comes in. So by the time left_max climbed to some height, the right side had already locked in a wall at least that tall. In short: whenever the left bar is the shorter of the two, its left wall is guaranteed not to exceed the right side's tallest wall, so left_max alone decides the water. The symmetric statement covers the other branch. That is why one number per side is enough — no lookahead required.

Worked example:height = [0, 1, 0, 2]
- left=0 (0), right=3 (2). Left bar shorter. left_max = 0. Water here: 0 − 0 = 0. left→1.
- left=1 (1), right=3 (2). Left bar shorter. left_max = 1. Water: 1 − 1 = 0. left→2.
- left=2 (0), right=3 (2). Left bar shorter. left_max stays 1. Water: 1 − 0 = 1. left→3.
- left meets right, stop. Total trapped: 1 (the dip at position 2, held by the 1 on its left and the 2 on its right).

Slotting it into the family

The template again: (a) we read the two end bars and compare them; (b) we move the shorter side; (c) we record water using that side's running max. Like Container With Most Water, the enabling property is not sorting — it is that the quantity at each position is bottlenecked by the smaller of two boundary walls. That bottleneck is what lets us commit the shorter side early and forget it. When you meet a problem about levels, areas, or capacities pinned between a left boundary and a right boundary, that "limited by the weaker side" shape is your cue that converging from both ends — sometimes with a running max in hand — will collapse an O(N²) or O(N)-space solution down to a single O(1)-space pass.

Interactive Strategy Visualization