Easy understanding python solution with two-pass


  • 0
    Z

    '''
    class Solution(object):
    def trap(self, height):

       # :type height: List[int]
       # :rtype: int
        if len(height) <= 2:
            return 0
        
        n = len(height)
        front = [0]
        back = [n-1]
        res = 0
        for i in range(n):
            if height[i] > height[front[-1]]:
                front.append(i)
        
        for i in range(n-1,-1,-1):
            if height[i] > height[back[-1]]:
                back.append(i)
    
            
        for i in range(len(front)-1):
            res += height[front[i]] * (front[i+1] - front[i] - 1) - sum(height[front[i]+1:front[i+1]])
        for i in range(len(back)-1):
            res += height[back[i]] * (back[i] - back[i+1] - 1) - sum(height[back[i]-1:back[i+1]:-1])
    
        if back[-1] > front[-1]:
            res += height[back[-1]] * (back[-1] - front[-1] - 1) - sum(height[front[-1]+1:back[-1]])
        return res
    

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.