Skip to content

Instantly share code, notes, and snippets.

@deque-blog

deque-blog/trap_water_3.py

Created March 7, 2020 09:48
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save deque-blog/023475d7a64dceca563a063ee7d75044 to your computer and use it in GitHub Desktop.
Save deque-blog/023475d7a64dceca563a063ee7d75044 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
trap_water_3.py
def trap(heights: List[int]) -> int:
right_heights = list(heights)
for i in reversed(range(len(right_heights)-1)):
right_heights[i] = max(right_heights[i], right_heights[i+1])
left_h = 0
total_volume = 0
for i in range(1, len(heights)-1):
h = heights[i]
left_h = max(heights[i-1], left_h)
right_h = right_heights[i+1]
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