Trapping Rain Water

Problem

Civil engineers model urban flooding by computing how much rainwater collects between buildings of varying heights. Given an array of non-negative integers representing an elevation map where each bar has width 1, compute how much water can be trapped after raining.

Input: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] → 6
Input: [4, 2, 0, 3, 2, 5]                    → 9
Input: [3, 0, 3]                              → 3

Solution

Approach: converging two pointers tracking a running max from each side.

Water above any bar equals min(left_max, right_max) - height[i], where the maxes are the tallest bars to its left and right. The trick that removes the two precomputed max arrays is this: at each step you only need to resolve the side whose running max is smaller, because that side is the binding constraint. The loop keeps left_max and right_max as the tallest bars seen from each end. When left_max <= right_max, the left wall is the shorter (or tied) boundary, so whatever sits at left is capped by left_max regardless of taller bars further right - it is safe to commit left_max - height[left] and advance left. Otherwise the right side is the bottleneck and the symmetric move applies.

The key correctness insight is that the smaller running max is a guaranteed lower bound on the true boundary for the bar being processed, so committing its water is never premature. Trace [3, 0, 3]: left_max=right_max=3, left<=right ties so step left onto the 0, left_max stays 3, add 3-0=3. Pointers meet, total is 3.

Edge cases: a flat array like [3, 3, 3] traps nothing because every current_max - height is 0; the maxes are seeded from the endpoints, so the first and last bars are correctly treated as walls and never count as holding water.

Complexity: O(n) time, O(1) space - a single converging pass with only the two pointers and two running maxes, no auxiliary arrays.