Hard Two Pointer Max Two Pointers
In plain English: Given a bar chart of heights, figure out how much rainwater gets trapped in the valleys between bars.
Water at any position = min(max_left, max_right) - height. Use two pointers: process from the side with the smaller max. That side's water level is determined since the other side is at least as tall.
Prompt
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.
Try to write it from scratch before scrolling down.
Solution
def trap(height):
l, r = 0, len(height) - 1
left_max = right_max = 0
water = 0
while l < r:
# process from the shorter side: its water level is fully determined
# because the opposite side is at least as tall
if height[l] < height[r]:
left_max = max(left_max, height[l])
water += left_max - height[l] # gap between max seen and current bar
l += 1
else:
right_max = max(right_max, height[r])
water += right_max - height[r]
r -= 1
return water
# Test: trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
# Test: trap([4,2,0,3,2,5]) == 9