Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
n == height.length, 1 <= n <= 2 * 10^4, 0 <= height[i] <= 10^5
Use two pointers. Track max height from left and right. Water at each position = min(leftMax, rightMax) - height[i]. Move pointer with smaller max inward.
def trap(height):
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
water = 0
while left < right:
if left_max < right_max:
left += 1
left_max = max(left_max, height[left])
water += left_max - height[left]
else:
right -= 1
right_max = max(right_max, height[right])
water += right_max - height[right]
return water