Leetcode 42. Trapping Rain Water

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

This is another subtle problem. The normal thought of layer to layer recursion is too slow.

To get the amount of water, we should know if there are walls on the two sides of the spot. If we know the max heights on both sides, hl and hr, amount of this spot = min(hl, hr) - h.

Solution:

# T:O(n) S:O(n)
class Solution:
    # @param {integer[]} height
    # @return {integer}
    def trap(self, height):
        L = len(height)
        if L == 0: return 0
        water = LH = RH = 0  # left higest and right highest
        LMH = [0]*L   # left most height
        for i in xrange(L):
            if height[i] > LH:
                LH = height[i]
            LMH[i] = LH
        for i in xrange(L-1,-1,-1):
            if height[i] > RH:
                RH = height[i]   # right most height
            if min(LMH[i], RH) > height[i]:
                water += min(LMH[i], RH) - height[i]
        return water

Run Time: 76 ms