my recursive javascript solution


  • 0
    E

    Why not use a recursive approach with O(n) time complexity:

    var trap = function(height) {
        var lp=0, rp=height.length-1, trp=0;
        for(var c=1; c < height.length - 2; c++){
    		if(c < rp && height[c]>=height[lp]) lp=c;
    		if((height.length-1-c) > lp && height[height.length-1-c]>=height[rp]) rp=height.length-1-c;
    	}
        var level = Math.min(height[lp], height[rp]);
        for(var i=lp+1; i<rp; i++) if(height[i] < level) trp = trp + level - height[i];
        if(lp > 1){
            var la = height.slice(0, lp+1);
            trp = trp + trap(la);
        }
        if(rp < height.length-2){
            var ra = height.slice(rp, height.length);
            trp = trp + trap(ra);
        }
        return trp;
    };
    

Log in to reply
 

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