Straightforward O(n) solution python


  • 1
    G

    A straightforward solution is to move from left to right and calculate water collected if the left elevation is the smaller one. Do the same thing from the right assuming right to be the smaller one, taking care of equal elevations

        def trap(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            if height == None or len(height) == 0 : return 0
            #move front and collect all rainwater
            water,puddle = 0,0
            prev = height[0]
            for each in range(1,len(height)):
                if height[each] >= prev: #collected only when 2 elevations are high enough
                    #print water,s
                    water+=puddle 
                    puddle = 0
                    prev = height[each]
                else:
                    puddle+= prev-height[each] #possible rainwater collection
                    
            #move from the other direction and collect the water
            puddle = 0
            prev = height[-1]
            for each in range(len(height)-2,-1,-1):
                
                if height[each] > prev: #same as before but dont double count '=' heights
                    print water,puddle
                    water+=puddle
                    puddle=0
                    prev = height[each]
                else:
                    puddle+= prev-height[each]
            return water

Log in to reply
 

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