Skip to content

Instantly share code, notes, and snippets.

@deque-blog

deque-blog/trap_water_1.py

Last active March 7, 2020 09:45
Show Gist options
  • Save deque-blog/13dcbd9720f692d6f5b38c9a7fb5a8ce to your computer and use it in GitHub Desktop.
Save deque-blog/13dcbd9720f692d6f5b38c9a7fb5a8ce to your computer and use it in GitHub Desktop.
Download ZIP
Raw
trap_water_1.py
def trap(heights: List[int]) -> int:
total_volume = 0
for i, h in enumerate(heights):
left_h = max(heights[:i], default=0)
right_h = max(heights[i+1:], default=0)
volume = max(0, min(left_h, right_h) - h)
total_volume += volume
return total_volume
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment