Two-Pointer Trapping Rain Water Simulation
Calculating fluid volume trapped between elevation barriers naively requires allocating two full prefix/suffix arrays. The Two-Pointer technique converges inward from both ends: whichever side has the lower running wall height dictates the local water level, running in $O(1)$ memory and $O(N)$ time 🌊🧱⚡.
def rain_trap(h):
l, r = 0, len(h) - 1
l_max, r_max = h[l], h[r]
water = 0
while l < r:
if l_max < r_max:
l += 1; l_max = max(l_max, h[l]); water += l_max - h[l]
else:
r -= 1; r_max = max(r_max, h[r]); water += r_max - h[r]
return water
print("Trapped Water:", rain_trap([3, 0, 2, 0, 4]))
# 29. Two-Pointer Trapping Rain Water Simulation Trapping Rain Water is a quintessential algorithm benchmark that demonstrates how moving pointers inward from boundaries can eliminate temporary array buffers and redundant passes 🛑. ```python # The Elevation Profile: # Index: 0 1 2 3 4 5 6 7 8 9 10 11 # Height:0 1 0 2 1 0 1 3 2 1 2 1 # Water: 0 0 1 0 1 2 1 0 0 1 0 0 -> Total = 6 units ``` ### The Inward Convergence Invariant At any index $i$, the height of trapped water is strictly: $$\text{Water}_i = \min(\text{left\_max}_i, \text{right\_max}_i) - \text{height}_i$$ - If `left_max < right_max`, we know with absolute mathematical certainty that `left_max` is the true limiting barrier for the left pointer position! - The right peak is higher, meaning water cannot leak out to the right. - Therefore, we can advance `left`, update `left_max`, add `left_max - height[left]`, and never look back: **$O(1)$ auxiliary space** 🌊🧱⚡! --- ### Interactive Pop-Quiz 🧠#### Why can the Two-Pointer algorithm safely calculate water on the side with the smaller running max without knowing the exact height of peaks in the middle? - [ ] Because the opposite wall is guaranteed to be taller or equal, ensuring that water cannot spill over that higher side 🌊 - [ ] Because water gravity flows from right to left - [ ] Because heights are stored as unsigned integers - [ ] It relies on quantum superposition --- ### Practical Challenge 🎯 Implement `trap_rain_water(heights: list[int]) -> int` using the optimal Two-Pointer approach ($O(N)$ time, $O(1)$ auxiliary space). Test with elevation map `[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]` (expect 6 units) and `[4, 2, 0, 3, 2, 5]` (expect 9 units). Assert both calculations and print results. <details> <summary>Solution</summary> ```python def trap_rain_water(heights: list[int]) -> int: if not heights: return 0 left, right = 0, len(heights) - 1 left_max, right_max = heights[left], heights[right] trapped_water = 0 while left < right: if left_max < right_max: left += 1 left_max = max(left_max, heights[left]) trapped_water += left_max - heights[left] else: right -= 1 right_max = max(right_max, heights[right]) trapped_water += right_max - heights[right] return trapped_water map1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] map2 = [4, 2, 0, 3, 2, 5] w1 = trap_rain_water(map1) w2 = trap_rain_water(map2) assert w1 == 6 assert w2 == 9 print(f"Trapped water verified: map1={w1} units, map2={w2} units") ``` </details>