class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
l = [0] * n # l[i] := max(height[0..i])
r = [0] * n # r[i] := max(height[i..n))
for i, h in enumerate(height):
l[i] = h if i == 0 else max(h, l[i - 1])
for i, h in reversed(list(enumerate(height))):
r[i] = h if i == n - 1 else max(h, r[i + 1])
return sum(min(l[i], r[i]) - h
for i, h in enumerate(height))
leetcode
challenge
Here is the link for the problem:
https://leetcode.com/problems/trapping-rain-water/
Oldest comments (0)