Trapping Rain Water With Converging Boundary Maxima

This one is a Hard-rated classic reported from Amazon, Google, Apple interviews: "Trapping Rain Water". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Two Pointers pattern on sight. Part 12 of 12 in the Two Pointers arc.

The Problem

Given height describing an elevation map with bar width 1, compute how much water it traps after raining. The water above any bar equals the smaller of the tallest bars to its left and right, minus its own height — the question is computing that without two prefix-max arrays.

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

Recognizing the Two Pointers Pattern

Two pointers means walking a sequence with two indices that move based on a comparison — from both ends inward, or slow-and-fast in one direction. It turns brute-force pair scans that cost O(n²) into a single O(n) pass, and it is usually the intended answer whenever the input is sorted or can be sorted cheaply.

Per-cell water depends on maxima from both directions, which suggests O(n) precomputation — but converging pointers carry both running maxima at once. Whichever side's max is smaller is fully determined for its current cell, so that side can be resolved and advanced.

The Approach

Keep left_max and right_max while pointers converge. If left_max is smaller or equal, the water at left is exactly left_max - height[left] — the true right boundary can only be taller, so it cannot matter — bank it and advance. Otherwise resolve the right cell symmetrically.

This is the same eliminate-the-certain-side logic as Container With Most Water, applied per cell instead of per pair. Connecting the two out loud is a strong senior signal.

Python Solution

def trap(height: list[int]) -> int:
    """Total trapped rain water over the elevation map."""
    if not height:
        return 0
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0
    while left < right:
        if left_max <= right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]
    return water

Complexity

• Time: O(n) — each index is resolved exactly once by one of the pointers
• Space: O(1) — two pointers and two running maxima replace the prefix arrays

Interview Tips and Follow-Ups

• Ladder to rehearse: brute force O(n²), two prefix-max arrays O(n)/O(n), monotonic stack, then this O(n)/O(1). Naming all four is the flex.
• The stack variant computes water horizontally and is its own follow-up — know it exists and when it is asked (2D version setup).
• Trapping Rain Water II (2D with a heap) is the canonical escalation at Google — mention, do not derive, unless asked.

If this clicked, continue the Two Pointers arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.