42. Trapping Rain Water
An elevation map arrives as an integer array height: height[i] is the height of a bar of width 1 standing at position i. When rain falls, water pools in every dip that is walled in by taller bars on both sides. Return the total number of unit squares of water the map retains.
The physics in one line: the water column above position i rises to min(tallest bar to the left of or at i, tallest bar to the right of or at i), and anything above that spills over the lower wall. The bar's own height eats into that column, so position i holds cap − height[i] units (never negative).
Example 1:
Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Explanation: The dips at indices 2, 4, 5, 6 and 9 hold 1 + 1 + 2 + 1 + 1 = 6 units (see the figure).
Example 2:
Input: height = [4, 2, 0, 3, 2, 5]
Output: 9
Explanation: Every index between the walls of height 4 and 5 fills to level 4: (4−2) + (4−0) + (4−3) + (4−2) = 9.
Constraints:
- 1 ≤ height.length ≤ 2 * 10⁴
- 0 ≤ height[i] ≤ 10⁵
Hints:
Water sitting on top of position i is decided by exactly two numbers: the max height to its left and the max height to its right. The lower of the two is the water level there.
Precompute prefix maxima and suffix maxima in two sweeps; then one more sweep sums min(left[i], right[i]) − height[i].
For O(1) extra space, walk two pointers inward. Whichever side currently has the smaller running max is 'sealed' — its water level cannot be raised by anything on the far side — so you can settle that column immediately and advance.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Expected output: 6