Trapping Rain Water: The Staff-Level Classic

Concepts: pyTrappingRainWater, pyInvariantProof

Trapping Rain Water (LeetCode 42) is the canonical hard two-pointer problem. It appears in senior data engineering loops at Google, Amazon, and Netflix. The problem: given an array of non-negative integers representing an elevation map, compute how much water it can trap after raining. The brute force is O(n^2): for each position, find the tallest bar to its left and right, and the water at that position is min(left_max, right_max) - height. Two pointers gives you O(n) time, O(1) space. The key insight that most candidates miss: you do not need to know BOTH the left_max and right_max to compute water at a position. You only need to know that the OTHER side has a bar at least as tall as the side you are processing. If left_max is less than right_max, the water at the left pointer is determi