LeetCode 42 Trapping Rain Water - Problem Statement

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

With height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the answer is 6. Water fills the valleys between taller bars. At index 2, the bar height is 0, but water fills up to height 1 (limited by the left maximum).

Think about any single position: how much water can it hold? It depends on the tallest bar to its left and right.

Constraints: $1 \le n \le 2 \times 10^4$, heights from $0$ to $10^5$.