Trapping Rain Water

Water above an index is limited by the smaller of its tallest boundary on the left and right. Precomputing both maxima works in O(n) time and O(n) space, but the interview-quality solution uses two pointers. Keep left, right, leftMax, rightMax. If height[left] <= height[right], the right boundary is known to be at least the current left height, so leftMax alone determines water at left: update it or add leftMax-height[left], then advance left. Symmetrically process right otherwise. This invariant guarantees every index is finalized once, for O(n) time and O(1) extra space. Test empty input, monotonic heights, one bowl, and equal-height walls. Use a wide accumulator if heights and n can make the sum overflow.