LeetCode 42 · Two Pointers · concepts: two-pointers, prefix-sum

Problem

Given an elevation map height, compute how much rainwater is trapped between the bars.

height = [0,1,0,2,1,0,1,3,2,1,2,1]  ->  6

The key fact — water above a single bar

Water sitting on top of bar i is bounded by the tallest wall to its left and the tallest wall to its right; it fills to the lower of those two, minus the bar’s own height:

water[i] = max(0, min(maxLeft[i], maxRight[i]) - height[i])

The total is the sum over all bars. Every solution is just a way of computing maxLeft and maxRight efficiently.

Approach 1 — precompute left/right max arrays

Two passes fill maxLeft and maxRight; a third sums the trapped water.

def trap(height):
    n = len(height)
    if n == 0: return 0
    maxLeft, maxRight = [0]*n, [0]*n
    maxLeft[0] = height[0]
    for i in range(1, n):
        maxLeft[i] = max(maxLeft[i-1], height[i])
    maxRight[-1] = height[-1]
    for i in range(n-2, -1, -1):
        maxRight[i] = max(maxRight[i+1], height[i])
    return sum(max(0, min(maxLeft[i], maxRight[i]) - height[i]) for i in range(n))

Time O(n), space O(n). Clear, and this is the prefix/suffix-aggregate idea (directional running maxima) — same shape as Product Except Self.

Approach 2 — two pointers, O(1) space (optimal)

Carry running leftMax and rightMax in two variables while converging from both ends. The trick: process whichever side has the smaller running max, because on that side the water level is definitely determined by that smaller max — the opposite wall is guaranteed at least as tall, so it can’t be the limiting factor.

def trap(height):
    l, r = 0, len(height) - 1
    leftMax, rightMax = 0, 0
    total = 0
    while l < r:
        if height[l] < height[r]:            # left side is the shorter wall -> left bounds the water
            leftMax = max(leftMax, height[l])
            total += leftMax - height[l]
            l += 1
        else:
            rightMax = max(rightMax, height[r])
            total += rightMax - height[r]
            r -= 1
    return total

Time O(n), space O(1).

Why “process the smaller side” is valid

When height[l] < height[r], whatever the true right max is, it’s ≥ height[r] > height[l], hence ≥ everything on the left so far. So the water over the left pointer is limited solely by leftMax — you can commit to it without knowing the exact right max. Symmetric on the other side. That’s what lets two scalars replace the two O(n) arrays.

Complexity summary

ApproachTimeSpace
Left/right max arraysO(n)O(n)
Two pointersO(n)O(1)
Monotonic stackO(n)O(n)

(A monotonic stack solves it too, filling water layer by layer — good to mention as an alternative framing.)

Key insight

Water at a bar = min(left-max, right-max) − height. The two-pointer optimization rests on a subtle proof: the side with the smaller running max is fully determined, so you can advance it and bank its water immediately. This is the hardest of the two-pointer problems precisely because the correctness argument, not the code, is the challenge.

↑ Back to NeetCode 150 — Solved