BinarySearch 0090 Rain Catcher

Problem statement

https://binarysearch.com/problems/Rain-Catcher/

Solution

Equal to Leetcode 0042. Trapping Rain Water

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, H):
        left = list(accumulate(H, max))
        right = list(accumulate(H[::-1], max))[::-1]
        return sum(min(i, j) - k for i, j, k in zip(left, right, H))