Trapping Rain Water

Problem

You are given an array height where height[i] is the height of a bar of width 1 standing at position i, forming an elevation profile. After it rains, water settles in the valleys between taller bars. Return the total number of unit squares of water the profile traps.

Water above position i rises to the level of the shorter of the tallest bar to its left and the tallest bar to its right — anything higher spills off the ends.

Examples

Example 1

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

One unit sits at index 2, one at index 4, two at index 5, one at index 6, one at index 9.

Example 2

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

The walls of height 4 and 5 trap 2 + 4 + 1 + 2 = 9 units over indices 1–4.

Example 3

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

Index 1 holds water up to min(3, 2) = 2, i.e. 1 unit. Monotonic profiles trap nothing.

Constraints

• 1 <= height.length <= 2 * 10^4
• 0 <= height[i] <= 10^5
• An O(n^2) rescan per position is too slow; O(n) time is expected, and O(1) space is achievable.

Think about it first

TL;DR

Two pointers carrying running maxima — O(n) time, O(1) space (prefix/suffix max arrays give O(n)/O(n); a monotonic stack also runs O(n)/O(n)).

Approach 1 — Brute force

For every position, rescan the whole array for the tallest bar on each side, then apply the water formula directly.

from typing import List

def trap(height: List[int]) -> int:
    n = len(height)
    total = 0
    for i in range(n):
        left_max = max(height[: i + 1])
        right_max = max(height[i:])
        total += min(left_max, right_max) - height[i]
    return total

Complexity: O(n^2) time, O(1) space. Each of up to 2 * 10^4 positions rescans up to 2 * 10^4 bars — ~4 * 10^8 operations, past the limit.

Approach 2 — Prefix/suffix maximum arrays

The insight: the water level over i is min(max_left[i], max_right[i]), and both quantities are classic prefix computations — each is derivable from its neighbor in O(1). Two sweeps precompute them; a third sweep sums the water.

from typing import List

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

    left_max = [0] * n
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])

    right_max = [0] * n
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    return sum(
        min(left_max[i], right_max[i]) - height[i]
        for i in range(n)
    )

Walkthrough on height = [4, 2, 0, 3, 2, 5]:

• left_max = [4, 4, 4, 4, 4, 5]
• right_max = [5, 5, 5, 5, 5, 5]
• Water per index: 0, 2, 4, 1, 2, 0 → total 9.

Complexity: O(n) time, O(n) space for the two arrays.

Approach 3 — Two pointers with running maxima

The insight: you never need both maxima exactly — only the smaller one. Keep pointers at both ends with running maxima left_max and right_max. When left_max < right_max, the bar producing right_max already stands somewhere right of the left pointer, so the true right-side maximum at that cell is ≥ right_max > left_max — the min is left_max, decided without ever scanning the right side. Settle the left cell and advance; mirror the argument on the other side.

from typing import List

def trap(height: List[int]) -> int:
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    total = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            total += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            total += right_max - height[right]
            right -= 1
    return total

Walkthrough on height = [3, 1, 2]:

(Comparing height[left] < height[right] is equivalent to comparing the running maxima: the side with the smaller current bar is the side whose running max is the binding one.)

Complexity: O(n) time — each step retires one index. O(1) space.

Approach 4 — Monotonic stack (horizontal layers)

The insight: instead of summing water column by column, sum it layer by layer. Keep a stack of indices with decreasing heights — a monotonic stack, the classic structure for nearest-taller-element problems. When a bar taller than the stack top arrives, the top is a valley floor: it’s bounded by the new bar on the right and the next stack element on the left, so a horizontal slab of water can be accounted for and the floor popped.

from typing import List

def trap(height: List[int]) -> int:
    stack: List[int] = []          # indices, heights strictly decreasing
    total = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            floor = stack.pop()
            if not stack:
                break              # no left wall for this floor
            left_wall = stack[-1]
            width = i - left_wall - 1
            depth = min(height[left_wall], h) - height[floor]
            total += width * depth
        stack.append(i)
    return total

Walkthrough on height = [4, 2, 0, 3, 2, 5]:

1. Push 0(4), 1(2), 2(0).
2. i = 3 (3): pop 2(0) → walls 1(2) and 3 → width 1, depth min(2,3) - 0 = 2 → +2. Pop 1(2) → walls 0(4) and 3 → width 2, depth min(4,3) - 2 = 1 → +2. Push 3. (total 4)
3. i = 4 (2): 2 < 3, just push 4. Stack: 0(4), 3(3), 4(2).
4. i = 5 (5): pop 4(2) → walls 3(3), width 1, depth 1 → +1. Pop 3(3) → walls 0(4), width 4, depth min(4,5) - 3 = 1 → +4. Pop 0(4) → stack empty, stop. (total 9)

Complexity: O(n) time — every index is pushed and popped at most once. O(n) space for the stack.

Common pitfalls

• Clamping: with precomputed arrays that include height[i] itself, min(left_max, right_max) - height[i] is never negative — but if you define the maxima as strictly-beside maxima, it can be; know which definition you’re using.
• Two-pointer side choice: you must process the side with the smaller bar; processing the larger side uses a running max that isn’t yet guaranteed to bound the cell.
• Stack version width/depth: width is i - left_wall - 1 (exclusive of both walls) and depth subtracts the popped floor, not the wall — both off-by-ones are common.
• Edge profiles: monotonic or length-<3 inputs trap zero; make sure your loop bounds return 0 rather than crashing.

Pattern takeaway

The two-pointer version generalizes a useful idea: when the answer at a position is the min (or max) of a left-quantity and a right-quantity, you can often walk in from both ends and finalize whichever side is currently bound by the smaller value — the unseen side can only make the min argument stronger, never weaker. This is the same reasoning as Container With Most Water, and it is the standard route from an O(n)-space prefix/suffix solution down to O(1).