Two Pointers
LC #42Hard
Trapping Rain Water
Two Pointers
AmazonGoogleMetaBloombergAppleProblem
Given an elevation map, compute how much water it can trap after raining.
arraytwo-pointersdynamic-programming
Constraints
- ›1 ≤ n ≤ 2 × 10⁴
- ›0 ≤ height[i] ≤ 10⁵
Example
Input
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]Output
6Why
Trapped water at each index (0-based): 0,0,1,0,1,2,1,0,0,1,0,0 → total = 6