Trapping Rain Water - calculate amount of water trapped between array elements

Why This Problem: Teaches two-pointer and prefix reasoning. Water at i = min(max_left, max_right) - height[i].

Approaches: (1) Precompute max_left, max_right arrays—O(n) time, O(n) space. (2) Two pointers—O(n) time, O(1) space: move from smaller side, track max on that side. Water = max_side - height.

Data Eng Analogy: 'Valleys' in time-series—local minima between peaks. Fill pattern similar to interpolating missing values between known bounds.

def trap(height):
l, r, lmax, rmax, water = 0, len(height)-1, 0, 0, 0
while l < r:
if height[l] < height[r]:
lmax = max(lmax, height[l])
water += lmax - height[l]
l += 1
else:
rmax = max(rmax, height[r])
water += rmax - height[r]
r -= 1
return water