A bar can hold some water atop if there are left and right supports for it.
So, we can compute water on top of each bar and sum up.
Time: 
class Solution:
def trap(self, height: List[int]) -> int:
def max_height(start, end):
h = 0
for i in range(start, end+1):
h = max(h, height[i])
return h
water = 0
for i, h in enumerate(height):
left_support = max_height(0, i - 1)
right_support = max_height(i + 1, len(height)-1)
water += max(0, min(left_support, right_support) - h)
return water
We could pre-compute left and right support for each index.
Time: 
class Solution:
def trap(self, height: List[int]) -> int:
left_supports = [0] * len(height)
left_supports[0] = height[0]
for i in range(1, len(height)):
left_supports[i] = max(height[i], left_supports[i-1])
right_supports = [0] * len(height)
right_supports[len(height)-1] = height[-1]
for i in range(len(height)-2, -1, -1):
right_supports[i] = max(height[i], right_supports[i+1])
water = 0
for i, h in enumerate(height):
left_support = left_supports[i-1] if i-1 >= 0 else 0
right_support = right_supports[i+1] if i+1 < len(height) else 0
water += max(0, min(left_support, right_support) - h)
return water
With two pointers moving from two ends, we can find the left and the right supports for a bar as we compute the water atop it. Since between the two supports the shorter one matters, we always advance the pointer on the shorter side.
Time:
class Solution:
def trap(self, height: List[int]) -> int:
water = 0
left_max, right_max = 0, 0
left, right = 0, len(height)-1
while left < right:
if height[left] <= height[right]:
left_max = max(left_max, height[left])
water += ( left_max - height[left] )
left += 1
else:
right_max = max(right_max, height[right])
water += (right_max - height[right])
right -= 1
return water
unreasonably effective 
Leave a comment