Trapping Rain Water


  • 0
    A

    Click here to see the full article post


  • 0
    T

    The explanation to your last approach is confusing.. Specifically the algorithm when height[left] > height[right] you ask to increment left but in your code.. you are decrementing right in that case..


  • 0
    A

    @thalaivva Yes sir, that was a mistake in the algorithm. Thanks for rectifying the issue. It has been corrected now. :D


  • 0
    R

    There's an O(n) runtime and O(1) space algorithm too. It works by tracking the space not filled by water, then subtracting that from the "box" formed by the length of the array and the maximum height. Iterate through the height array 3 times:

    • Starting from the left, sum up the open space under the maximum height which is entirely to the left of all blocks. This is done by tracking the maximum height you've seen so far, and each time that a new height exceeds that, increase the amount of open space by the product of the difference between the new height and the old, and the horizontal distance between the end of the array and your current location.
    • Repeat the previous, except this time start from the right end and track how much open space is entirely to the right in the same way.
    • Find the sum of all values in the height array (i.e., how many square units are filled by blocks)

    Sum the non-water area you got from those three iterations, then subtract the sum from the product of the maximum height and the length of the height array. That gives you the amount of water your structure holds.

    In Python (1st and 3rd iterations described above are combined in this example):

    #Python
    class Solution(object):
        def trap(self, heights):
            """
            :type heights: List[int]
            :rtype: int
            """
            # openSum = amount of confirmed open space we have so far (area under maxHeight)
            # filledSum = amount of space filled with blocks
            # maxHeight = height of highest wall found so far
            openSum=0
            maxHeight = 0
            filledSum = 0
            
            # Frontwards
            for i in range(len(heights)):
                if heights[i] > maxHeight:
                    openSum = openSum + ((heights[i]-maxHeight)*(i))
                    maxHeight = heights[i]
                filledSum = filledSum + heights[i] # Track how many blocks there are
            
            maxHeight = 0
            
            # Backwards
            for i in range(len(heights)-1,-1,-1):
                if heights[i] > maxHeight:
                    openSum = openSum + ((heights[i]-maxHeight)*(len(heights)-(i+1)))
                    maxHeight = heights[i]
            
            return (maxHeight*len(heights))-(openSum+filledSum) # Size of full box, minus open space, minus space filled with blocks
    
    
    

    You could also use 2 pointers like in Solution #4 to combine all 3 iterations into one, but that doesn't change the time complexity.


  • 1
    R

    The DP solution certainly does not need O(n) space.

    1. We iterate forwards as usual, keeping the index of the last maximal height. Let this index be called peak
    2. We iterate backwards until peak, keeping track of the last seen maximum, and subtracting excess rainwater

    Where excess = peak - currentMaximum

    /**
     * @param {number[]} height
     * @return {number}
     */
    var trap = function(height) {
        if (height.length < 1) return 0
        peak = 0
        currMax = height[0]
        rain = 0
        for (i = 0; i < height.length; i++) {
            currHeight = height[i]
            
            if (currHeight < currMax) {
                rain += currMax - currHeight
            } else {
                currMax = currHeight
                peak = i
            }
        }
        
        currMax = height[height.length - 1]
    
        for (i = height.length - 1; i > peak; i--) {
            currHeight = height[i]
            if (currHeight > currMax) {
                currMax = currHeight
            }
            
            console.log('subtracting', (height[peak] - currMax), 'at', i)
            rain -= height[peak] - currMax
        } 
        
        return rain
    };```

Log in to reply
 

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