Problem statement

https://leetcode.com/problems/trapping-rain-water/

Solution

To solve this problem, we need to understand what does trapping means. Imagine that we have some index i, how to evaluate amount of water we have in this index? There are two constraints: water can go to the left and to the right. Imagine for the moment, that we have infinite wall in the left, than what is the level of water it can rise? It is the maximum value from our map to the right of our index! The same logic works if we add infinite wall in the left. What to do now if we do not have infninite walls? We need to find minimum between the highest point to the left and the highest point to the right and this will solve the problem!

Complexity

We have O(n) time and memory complexity.

Code

class Solution:
    def trap(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))

Oneliner

return sum(min(i, j) - k for i, j, k in zip(accumulate(H, max), list(accumulate(H[::-1], max))[::-1], H))