Javascript 314 / 315 solution (times out on last test)


  • 0
    C
    /**
     * @param {number[]} height
     * @return {number}
     */
    var trap = function(h) {
    	var water = 0;
    	var used = {};
        for (var i = 0; i < h.length; i++) {
        	var leftT = h[i];
        	var leftIdx = i;
        	if (leftT) {
        		var foundGt = false;
        		var rightT = 0;
        		var rightIdx = -1;
        		for (var j = i + 1; j < h.length; j++) {
        		    if (!foundGt && h[j] > leftT) {
        		        foundGt = j;
        		    }
        			if (h[j] && h[j] > h[j-1] && h[j] > rightT) {
        				var rightT = h[j];
        				var rightIdx = j;
        				var pool = calculatePoolSize(h, leftIdx, rightIdx, leftT, rightT, used);
        				water += pool;
        			}
        		}
        		if (foundGt) {
        		    i = foundGt - 1;
        		}
        	}
        }
        return water;
    };
    
    
    function calculatePoolSize(h, leftIdx, rightIdx, leftT, rightT, used) {
        var sharedH = leftT < rightT ? leftT : rightT;
        var pool = 0;
        for (var i = leftIdx + 1; i < rightIdx; i++) {
        	for (var j = h[i]+1; j <= sharedH; j++) {
        		if (!used[i + '-' + j]) {
        			used[i + '-' + j] = true;
        			pool++;
        		}
        	}
    	}
    	return pool;
    }
    

Log in to reply
 

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