LC #42Hard

Trapping Rain Water (Stack)

Monotonic Stack

AmazonGoogleMeta

Problem

Same problem as Trapping Rain Water (LC 42) — compute how much water an elevation map can trap after raining — but solved with a monotonic stack instead of two pointers. The stack approach processes water layer-by-layer horizontally, useful for building intuition from a different angle.

arraystacktwo-pointers

Constraints

›1 ≤ n ≤ 2 × 10⁴
›0 ≤ height[i] ≤ 10⁵

Example

Inputheight = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Output6

Why

Same as two-pointer approach but using a stack to find valley boundaries

Trapping Rain Water (Stack)

Problem

Constraints

Example

Hints — reveal one at a time