1 / 5
We're always moving the pointer on the side with the smaller height.
Comparing the current heights tells us which side is safe to process right now.
Historical maxes are what we actually use to calculate trapped water.
We pick the side with the smallest current height because that's the side where we're confident that the opposite side won't be interfering with our calculation.
class Solution:
def trap(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
left_max = right_max = 0
water = 0
while left < right:
if height[left] <= height[right]:
if height[left] >= left_max:
left_max = height[left]
else:
water += left_max - height[left]
left += 1
else:
if height[right] >= right_max:
right_max = height[right]
else:
water += right_max - height[right]
right -= 1
return water