Optimal Two-Pointer Approach & Code:
- Maintain two pointers inward from left and right, tracking left_max and right_max boundaries to calculate trapped water in O(1) space.
def trap_rain_water(height: list[int]) -> int:
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
total_water = 0
while left < right:
if left_max < right_max:
left += 1
left_max = max(left_max, height[left])
total_water += left_max - height[left]
else:
right -= 1
right_max = max(right_max, height[right])
total_water += right_max - height[right]
return total_water
Complexity & Key Logic:
- Time Complexity: O(N) single pass visiting each bar once.
- Space Complexity: O(1) auxiliary space.
- Algorithm Details:
- Water trapped at any index is determined by min(max_left, max_right) - height[i].
- By advancing the pointer with the smaller boundary, we know that the other side is guaranteed to be taller, so water capacity is bounded strictly by the smaller maximum.