Trapping Rain Water

The picture suggests moving inward from both ends. The proof requires more: finalize only the side whose limiting boundary is already certified.

For an elevation map of unit-width, non-negative bars, the two-pointer solution runs in O(n) time and O(1) auxiliary space. It maintains two running boundary maxima, narrows an unresolved interior interval, and calculates each interior bar exactly once.

State the contract and the per-index formula

For a bar at index i, trapped water depends on the tallest boundary available on each side:

• left_max[i]: tallest bar from the left through i
• right_max[i]: tallest bar from i through the right

The water above index i is:

water[i] = max(0, min(left_max[i], right_max[i]) - height[i])

The shorter boundary controls the water level. If the shorter boundary is height 4 and the current bar is height 2, that position contributes 2 units, regardless of how much taller the other boundary is.

The outermost bars contribute zero because they do not have bars on both sides. The answer is the sum of the water above all interior positions.

The optimization target is clear:

• scan the array once,
• keep only two running maxima,
• accumulate the answer,
• use no arrays proportional to n.

Use slower solutions to expose the missing state

The direct brute-force approach scans outward from every index:

for i in range(n):
    left_max = max(height[:i + 1])
    right_max = max(height[i:])
    total += max(0, min(left_max, right_max) - height[i])

Each maximum scan can take linear time. Repeating it for every position produces O(n²) time. The formula is correct; repeatedly rediscovering the same boundaries is the problem.

Prefix and suffix maxima

The first useful optimization stores that repeated work.

Build:

• left_max[i]: maximum height from 0 through i
• right_max[i]: maximum height from i through n - 1

Then each position can be evaluated in constant time using the original formula.

For the canonical input:

height    = [0,1,0,2,1,0,1,3,2,1,2,1]
left_max  = [0,1,1,2,2,2,2,3,3,3,3,3]
right_max = [3,3,3,3,3,3,3,3,2,2,2,1]

At index 5:

min(left_max[5], right_max[5]) - height[5]
= min(2, 3) - 0
= 2

Summing all positions gives 6.

This formulation takes O(n) time and O(n) space. It is not wasted work. I often use it as a correctness oracle while debugging the constant-space version. When two implementations disagree, the extra arrays make the boundary state visible instead of forcing you to reconstruct it from pointer movement.

The remaining question is whether both arrays are necessary.

Derive the two-pointer state

The two-pointer method divides the array into three regions:

1. a finalized region on the left,
2. an unresolved interior interval,
3. a finalized region on the right.

The outermost bars are seeded as boundary evidence because their contribution is already known to be zero.

Use these variables:

• left: first index in the unresolved interval
• right: last index in the unresolved interval
• left_max: tallest bar in the finalized left region
• right_max: tallest bar in the finalized right region
• total: water assigned to finalized interior positions

For an input with at least three bars, initialize:

left = 1
right = n - 2
left_max = height[0]
right_max = height[n - 1]
total = 0

At each step, compare the running maxima, not merely height[left] and height[right].

That distinction matters. The current endpoint might be short while an earlier bar on the same side is tall. The running maximum is the boundary evidence accumulated so far.

If:

left_max <= right_max

resolve the current left position.

Otherwise, resolve the current right position.

For the left branch:

1. calculate water using left_max,
2. update left_max with height[left],
3. move left inward.

added = max(0, left_max - height[left])
total += added
left_max = max(left_max, height[left])
left += 1

For the right branch, mirror the operations:

added = max(0, right_max - height[right])
total += added
right_max = max(right_max, height[right])
right -= 1

The order is deliberate. The current bar is measured against the maximum from its already-finalized side. Only after measuring do we include the current bar in that maximum and remove its index from the unresolved interval.

Invariant: Before each iteration, [left, right] is exactly the unresolved interior interval. Every position outside it has an exact water contribution. left_max and right_max summarize the boundary evidence in the finalized regions.

The compact algorithm is:

left = 1
right = n - 2
left_max = height[0]
right_max = height[n - 1]
total = 0

while left <= right:
    if left_max <= right_max:
        total += max(0, left_max - height[left])
        left_max = max(left_max, height[left])
        left += 1
    else:
        total += max(0, right_max - height[right])
        right_max = max(right_max, height[right])
        right -= 1

return total

Prove why the shorter side is safe

The common explanation—“move the shorter wall”—is a useful memory aid, but it is incomplete. The algorithm compares running maxima because those maxima represent known boundary capacity.

Consider the left branch:

left_max <= right_max

left_max is the tallest bar in the finalized region to the left of the current position. right_max is a known boundary in the finalized region to the right, and it is at least as tall as left_max.

Therefore, the actual right-side maximum for the current position is at least right_max, which is at least left_max. The left boundary is already the limiting side. Any future bar discovered farther to the right can only make the right boundary taller; it cannot reduce the water level below left_max.

So the current left position contributes exactly:

max(0, left_max - height[left])

The current bar itself does not invalidate this calculation. If it is taller than left_max, the contribution is zero, and the update raises left_max for later positions.

The right branch is symmetric. If:

right_max < left_max

then a known left boundary reaches at least right_max. The current right position is limited by right_max, so its contribution can be finalized immediately.

The tie rule is arbitrary as long as it is consistent. With:

left_max <= right_max

ties resolve from the left. When both maxima are equal, either side has a known boundary at the same limiting height.

This is the important distinction:

• An endpoint has merely been observed when you know its raw height.
• A side is certified when its running maximum is no greater than a known boundary on the opposite side.

The pointer does not move because the picture looks symmetrical. It moves because one side's limiting boundary has been proved sufficient.

Dry-run both edges of a basin

Use:

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

The outer bars are seeded as boundaries:

left = 1
right = 4
left_max = 4
right_max = 5

The table records the state before processing each unresolved interior position:

left	right	left_max	right_max	Chosen side	Bar	Added water
1	4	4	5	left	2	2
2	4	4	5	left	0	4
3	4	4	5	left	3	1
4	4	4	5	left	2	2

Total:

2 + 4 + 1 + 2 = 9

Why can every position be resolved from the left? The known left boundary has height 4, and the known right boundary has height 5. The right side is already high enough to certify that the left boundary controls the entire remaining basin.

The basin's water level is therefore 4:

• above height 2: 2 units,
• above height 0: 4 units,
• above height 3: 1 unit,
• above height 2: 2 units.

Every interior position is processed once. The two outer positions were seeded as boundaries and contribute zero.

Shapes worth checking by hand

A monotonic increase such as:

[0, 1, 2, 3]

contains no basin, so every contribution is zero. The left maximum keeps rising while no lower interior position has a taller boundary on both sides.

A monotonic decrease behaves symmetrically:

[3, 2, 1, 0]

Again, the answer is zero.

Equal boundaries test the tie rule:

[3, 1, 3]

The initial maxima are both 3, so <= resolves the middle position from the left and adds 2. Resolving from the right would also be correct, but mixing tie rules makes traces harder to inspect.

These small shapes expose the classic bugs:

• moving both pointers on every iteration,
• measuring after moving the pointer,
• comparing against the current bar instead of the running maximum,
• updating the maximum before calculating the current contribution,
• allowing a negative contribution instead of clamping it to zero.

Implement the proof directly in Python

The Python implementation should make the invariant visible. Do not compress the two branches into clever expressions; the mirrored state transitions are the point.

def trap(height: list[int]) -> int:
    if len(height) < 3:
        return 0

    left = 1
    right = len(height) - 2
    left_max = height[0]
    right_max = height[-1]
    total = 0

    # [left, right] is the unresolved interior interval.
    while left <= right:
        if left_max <= right_max:
            total += max(0, left_max - height[left])
            left_max = max(left_max, height[left])
            left += 1
        else:
            total += max(0, right_max - height[right])
            right_max = max(right_max, height[right])
            right -= 1

    return total

The early return is not mathematically required, but it makes the contract explicit: fewer than three bars cannot contain an interior position.

The implementation failures to watch for are precise:

1. Comparing raw endpoint heights

   if height[left] <= height[right]:
   

   This ignores taller bars already processed on either side. The decision belongs to left_max and right_max.

2. Moving before measuring

   If left += 1 happens first, the original left bar is skipped. Pointer movement is the final step of processing that position.

3. Updating before measuring

   Raising left_max with the current bar before calculating its water can hide water that should be counted above that bar.

4. Omitting the clamp

   A bar taller than the current boundary contributes zero, not negative water.

5. Updating the wrong maximum

   The left branch updates left_max; the right branch updates right_max. The code is symmetric, but the state is not interchangeable.

For validation, compare this implementation against the prefix/suffix version on:

[
    [],
    [1],
    [1, 2],
    [0, 0, 0],
    [1, 2, 3, 4],
    [4, 3, 2, 1],
    [3, 1, 3],
    [4, 2, 0, 3, 2, 5],
    [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1],
]

When a result differs, log the complete state before each transition:

left, right, left_max, right_max, chosen side, added water

Debug the state first. Do not rewrite the algorithm because one trace exposed an incorrect assumption.

Compare complexity and alternative formulations

The two-pointer method is O(n) time because every iteration moves either left or right inward, and neither pointer moves backward. Across the whole run, each interior position is finalized exactly once.

It uses O(1) auxiliary space: the input remains in place, and the algorithm stores only a fixed number of integers.

Approach	Time	Auxiliary space	Best use
Repeated left/right scans	O(n²)	O(1)	Baseline, tiny inputs, differential testing
Prefix and suffix maxima	O(n)	O(n)	Clear derivation and reference implementation
Two pointers	O(n)	O(1)	Final constrained solution
Monotonic stack	O(n)	O(n)	Alternative formulation based on basin structure

The prefix/suffix method is easier to inspect because every boundary value is materialized. Its cost is memory proportional to the input.

A monotonic-stack solution also achieves linear time, but it stores unresolved bars and derives water when a right boundary closes a basin. That is a useful alternative, but its mechanism is different from the boundary-maxima derivation here.

The brute-force method remains useful for testing. For small random arrays, compare brute force, prefix/suffix maxima, and two pointers. A slow implementation can be a valuable test instrument even when it is not suitable for the final constraints.

This qualifies as a two-pointer technique for a specific reason: coordinated pointer movement removes positions whose contributions are already certified. Merely having two indices in a loop does not create the pattern. The decisive operation is finalization through a boundary comparison.

Check edge cases and extract the reusable rule

Before submitting, test the shapes that attack your assumptions:

• empty input or fewer than three bars,
• all-zero heights,
• strictly increasing heights,
• strictly decreasing heights,
• equal-height plateaus,
• one isolated dip such as [5, 0, 5],
• multiple basins with different boundary heights,
• a basin whose taller wall is discovered late,
• totals larger than any individual bar height.

That last case matters in fixed-width languages. The accumulator must have enough range for the sum, not merely for one height[i].

There is also a useful boundary with Container With Most Water. That problem chooses one pair of boundaries and maximizes one area. Trapping Rain Water sums independent depths above many positions. Both problems compare boundaries, but the objective and proof obligation differ:

• container: select one pair,
• rain water: finalize every interior position.

The transferable rule is broader than this array:

First derive the per-position limiting quantity. Then identify monotone summaries that make one bound known. Finally, remove only the side whose limiting boundary is certified.

For this problem, the limiting quantity is:

min(left_max, right_max) - height[i]

The monotone summaries are the running maxima. The certified side is the one with the smaller known maximum.

In an interview, state that invariant before writing the constant-space code. Then keep the prefix/suffix formulation available as a mental—or literal—reference against which the compressed state machine must agree.

Derive the quantity. Name the evidence. Finalize only what the evidence proves. That is the two-pointer water-trapping pattern.