Straightforward O(n) solution python

  • 1

    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
                    puddle = 0
                    prev = height[each]
                    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
                    prev = height[each]
                    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.