leetExpert
Practice

Trapping Rain Water

Module 10 · Two Pointers

Problem

Given an elevation map height, compute how much rain water it traps.

Examples

Example 1

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

Example 2

Inputheight = [4,2,0,3,2,5]Output9
text
        █
█   █░░░█ █
█ █░█░█░█░█ █        ░ = trapped water (first example)

Constraints

1 ≤ n ≤ 2·10⁴ · heights in [0, 10⁵].

Attempt it first

The module capstone, and a hard one. Do NOT start from Container With Most Water's pointer rule — start from physics: why does any single cell hold water? Get the per-cell formula first (Hint 1), build the O(n)-space solution honestly, and only then compress it to two pointers. Each stage is a legitimate interview answer; the progression is the point.