2026-09-22 — Trapping Rain Water

Difficulty: 🔴 Hard Pattern: Two pointers (or a monotonic stack) Time-box: 20 minutes

Problem

Given an array height of n non-negative integers representing the elevation map, where each bar has width 1, compute how much water it can trap after raining.

A column holds water up to the height of the shorter of the tallest bar to its left and the tallest bar to its right — and only if both exist and are taller than the column itself.

Examples

[0, 1, 0, 3, 9, 2, 3, 4, 5, 7, 3, 0, 5] -> 22
[4, 2, 0, 3, 2, 5]                      -> 9
[1, 0, 1]                               -> 1
[]                                        -> 0

Constraints

0 <= n <= 2 * 10^4, 0 <= height[i] <= 10^5.
O(n) time expected; the O(n²) "scan both sides per column" approach does not scale.
O(1) extra space is achievable (O(n) is acceptable).

Hint (open only if stuck after 10 minutes)

Keep two pointers at the ends and two running maxima. On each step, move the pointer under the SMALLER maximum inward: that maximum is the definitive water level for that column, because the far side is at least as tall as it. Add level - height[col] and update the maximum.

Solution

def trap(height: list[int]) -> int:
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0

    while left < right:
        if height[left] < height[right]:
            # The right side holds a bar at least as tall as left_max
            # will ever need to be: left_max is the binding level here.
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1

    return water

How it works. Each column's water level is min(max-to-left, max-to-right). The two-pointer trick avoids computing both maxima for every column: when the left side is the smaller, its maximum is final for that column — the unseen right side cannot lower the minimum below it. So that column is settled in O(1), and the pointer advances.

Complexity. Time: O(n) — each pointer moves at most n steps total. Space: O(1) — two maxima and two pointers.

Edge cases that matter. Empty array and single bar (0 water). Flat arrays and monotone arrays (no basin, 0 water). Deep narrow wells between two huge walls. A column exactly as tall as the binding maximum adds 0 — the >= vs > choice in the update does not matter, but the structure (compare against the CURRENT max, not the bar opposite) does.

Common wrong answer. Using the height of the OPPOSITE pointer as the water level (water += height[right] - height[left] when the left is lower). That works only when the taller pointer happens to sit on the true basin wall; on inputs like [4, 2, 0, 3, 2, 5] where the maximum sits at the very end, it overcounts. The running maxima are what make the per-column level correct no matter where the tallest bars are.

Found a mistake? Edit this page on GitHub.