Python 48ms O(n) Time O(1) space


  • 0

    Key is to use each local max as a pivot, setting the first pointer to each of these, and using a second pointer to find the next local max that is greater than or equal to the local max at the first pointer. The edge case we need to consider in doing this is when a local max is not resolved at the end (i.e [2,4,3,2,1,2,3] since there isn't wall greater than a height of 4 by the end). We can workaround this by setting the last local max (4 for the example stated earlier) as the end point then traverse the array in a reversed fashion from right to left. This will handle all local maxes that are lower than the last local max captured when traversing from the left.

        def trap(self, height):
            """
            :type height: List[int]
            :rtype: int
            """
            if not height: return 0
            i, j, s = 0, 1, 0
            while j < len(height):
                incr = 0
                while j < len(height) and height[j] < height[i]:
                    incr += height[i] - height[j]; j += 1
                if j >= len(height): break
                s += incr
                i = j; j += 1
            piv = i
            if piv < len(height):
                # Same loop as above, just backwards
                i, j = len(height)-1, len(height)-2
                while j >= piv: 
                    incr = 0
                    while j >= piv and height[j] < height[i]:
                        incr += height[i] - height[j]; j -= 1
                    if j < piv: break
                    s += incr
                    i = j; j -= 1
            return s
    

Log in to reply
 

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