JavaScript O(n) geometric solution


  • 0
    var trap = function(height) {
        let landArea = 0;
        let maxFromLeft = 0;
        let maxAreaFromLeft = 0;
        
        for (let h of height) {
            landArea += h;
            maxFromLeft = Math.max(maxFromLeft, h);
            maxAreaFromLeft += maxFromLeft;
        }
        
        let maxFromRight = 0;
        let maxAreaFromRight = 0;
        
        for (let i = height.length - 1; i >= 0; i--) {
            maxFromRight = Math.max(maxFromRight, height[i]);
            maxAreaFromRight += maxFromRight;
        }
        
        const boundingArea = height.length * maxFromLeft;
        const leftVoid = boundingArea - maxAreaFromLeft;
        const rightVoid = boundingArea - maxAreaFromRight;
        return boundingArea - leftVoid - rightVoid - landArea;
    };
    

    We have a mountain with a bunch of filled ponds. We'll hike (and swim) over the highest parts and subtract from that area the same mountain during a nasty drought.


Log in to reply
 

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