JavaScript Solution Summary


  • 0
    Z

    Solution #1 (Using DFS)

    /**
     * @param {number[][]} heightMap
     * @return {number}
     */
    var trapRainWater = function(heightMap) {
        let water = 0, minh = Array(heightMap.length).fill([]);
        for(let i in minh) minh[i] = new Array(heightMap[0].length).fill(0);
        // return minh;
        if(heightMap.length<3||heightMap[0].length<3) return water;
    	for(let i=0;i<heightMap.length;i++){
    		minh[i][0] = heightMap[i][0];
    		minh[i][heightMap[0].length-1] = heightMap[i][heightMap[0].length-1]; 
    	}
    	for(let j=0;j<heightMap[0].length;j++){
    		minh[0][j] = heightMap[0][j];
    		minh[heightMap.length-1][j] = heightMap[heightMap.length-1][j];    			
    	}
    	for(let i=1;i<heightMap.length-1;i++)
    		for(let j=1;j<heightMap[0].length-1;j++){
    			let min = Number.MAX_VALUE;
    			if(minh[i-1][j]!==0) min = Math.min(min, minh[i-1][j]);
    			if(minh[i+1][j]!==0) min = Math.min(min, minh[i+1][j]);
    			if(minh[i][j+1]!==0) min = Math.min(min, minh[i][j+1]);
    			if(minh[i][j-1]!==0) min = Math.min(min, minh[i][j-1]);    			
    			minh[i][j] = Math.max(heightMap[i][j], min);
    			//pass by
    			dfs(heightMap, minh, minh[i][j], i-1, j);    	 
    	    	dfs(heightMap, minh, minh[i][j], i, j-1);    	    	
    		}
    	
    	for(let i=1;i<heightMap.length-1;i++)
    		for(let j=1;j<heightMap[0].length-1;j++){
    			water += minh[i][j]-heightMap[i][j];
    		}
    	
    	return water;
    };
    
    var dfs = function(matrix, minh, h, i, j){
    	if(i===0||i==matrix.length-1||j===0||j==matrix[0].length-1) return;
    	if(minh[i][j]===0) return;
    	if(minh[i][j]>h&&minh[i][j]!=matrix[i][j]){
    		minh[i][j] = Math.max(matrix[i][j], h); 
    		dfs(matrix, minh, minh[i][j], i-1, j);
        	dfs(matrix, minh, minh[i][j], i+1, j);
        	dfs(matrix, minh, minh[i][j], i, j-1);
        	dfs(matrix, minh, minh[i][j], i, j+1);
    	}    	
    };
    

    Solution #2 (Using Queue)

    /**
     * @param {number[][]} heightMap
     * @return {number}
     */
    var trapRainWater = function(heightMap) {
        var q = new myQueue();
        var visited = [];
        var x = heightMap.length;
        if(!x) {
            return 0;
        }
        var y = heightMap[0].length;
        if(!y) {
            return 0;
        }
        //console.log("X=" + x + ", Y=" + y);
        var sum = 0;
        for(var i = 0; i < x; i++) {
            var temp = Array(y).fill(false);
            visited.push(temp);
        }
        for(var j = 0; j < y; j++) {
            q.push({value: heightMap[0][j], loc: [0, j]});
            visited[0][j] = true;
            q.push({value: heightMap[x-1][j], loc: [x-1, j]});
            visited[x-1][j] = true;
        }
        for(var i = 1; i < x-1; i++) {
            q.push({value: heightMap[i][0], loc: [i, 0]});
            visited[i][0] = true;
            q.push({value: heightMap[i][y-1], loc: [i, y-1]});
            visited[i][y-1] = true;
        }
        //q.print();
        while(!q.empty()) {
            var temp = q.pop();
            //console.log("process " + JSON.stringify(temp));
            var locx = temp.loc[0];
            var locy = temp.loc[1];
            var v = temp.value;
            if(locx !== 0) {
                if(!visited[locx-1][locy]) {
                    visited[locx-1][locy] = true;
                    if(heightMap[locx-1][locy] > v) {
                        q.push({value:heightMap[locx-1][locy], loc:[locx-1, locy]});
                        //console.log("Push11 " + heightMap[locx][locy+1] + " to [" + locx + ", " + locy + "]" );
                    } else {
                        sum += v - heightMap[locx-1][locy];
                        q.push({value:v, loc:[locx-1, locy]});
                        //console.log("Push12 " + v + " to [" + locx + ", " + locy + "]" );
                    }
                }
            }
            if(locx !== x-1) {
                if(!visited[locx+1][locy]) {
                    visited[locx+1][locy] = true;
                    if(heightMap[locx+1][locy] > v) {
                        q.push({value:heightMap[locx+1][locy], loc:[locx+1, locy]});
                        //console.log("Push21 " + heightMap[locx][locy+1] + " to [" + locx + ", " + locy + "]" );
                    } else {
                        sum += v - heightMap[locx+1][locy];
                        q.push({value:v, loc:[locx+1, locy]});
                        //console.log("Push22 " + v + " to [" + locx + ", " + locy + "]" );
                    }
                }
            }
            if(locy !== 0) {
                if(!visited[locx][locy-1]) {
                    visited[locx][locy-1] = true;
                    if(heightMap[locx][locy-1] > v) {
                        q.push({value:heightMap[locx][locy-1], loc:[locx, locy-1]});
                        //console.log("Push31 " + heightMap[locx][locy-1] + " to [" + locx + ", " + locy + "]" );
                    } else {
                        sum += v - heightMap[locx][locy-1];
                        q.push({value:v, loc:[locx, locy-1]});
                        //console.log("Push32 " + v + " to [" + locx + ", " + locy + "]" );
                    }
                }
            }
            if(locy !== y-1) {
                if(!visited[locx][locy+1]) {
                    visited[locx][locy+1] = true;
                    if(heightMap[locx][locy+1] > v) {
                        q.push({value:heightMap[locx][locy+1], loc:[locx, locy+1]});
                        //console.log("Push41 " + heightMap[locx][locy+1] + " to [" + locx + ", " + locy + "]" );
                    } else {
                        sum += v - heightMap[locx][locy+1];
                        q.push({value:v, loc:[locx, locy+1]});
                        //console.log("Push42 " + v + " to [" + locx + ", " + locy + "]" );
                    }
    
                }
            }
        }
        return sum;
    };
    
    var myQueue = function() {
        this.cache = [];
    }
    
    myQueue.prototype.push = function(n) {
        var i;
        for(i = 0; i < this.cache.length; i++) {
            if(n.value < this.cache[i].value) {
                break;
            }
        }
        this.cache.splice(i, 0, n);
    };
    
    myQueue.prototype.pop = function() {
       return this.cache.shift(); 
    };
    
    myQueue.prototype.empty = function() {
        return this.cache.length === 0? true:false;
    }
    
    myQueue.prototype.print = function() {
        console.log(JSON.stringify(this.cache));
    }
    

    Solution #3 (Using Heap)

    function Heap(less) {
        this.heap = []
        this.less = less
    }
    
    Heap.prototype.exch = function(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
    }
    
    Heap.prototype.parent = function(x) {
        return (x-1) >> 1
    }
    
    Heap.prototype.swim = function(x) {
        while (x>0) {
            let p = this.parent(x)
            // console.log(this.heap[p], this.heap[x], this.less(this.heap[p],this.heap[x]))
            if (this.less(this.heap[p], this.heap[x])) {
                this.exch(p, x)
                x = p
            } else {
                break
            }
        }
    }
    
    Heap.prototype.sink = function(x) {
        while(2*x+1<this.heap.length) {
            let c = 2*x+1
            if (c+1<this.heap.length && this.less(this.heap[c], this.heap[c+1])) {
                c += 1
            } 
            
            if (this.less(this.heap[x], this.heap[c])) {
                this.exch(x, c)
                x = c
            } else {
                break
            }
        }
    }
    
    Heap.prototype.push = function(v) {
        this.heap.push(v)
        this.swim(this.heap.length-1)
        // console.log(v, this.heap)
    }
    
    Heap.prototype.size = function() {
        return this.heap.length
    }
    
    Heap.prototype.peak = function() {
        return this.heap.length > 0 ? this.heap[0] : null
    }
    
    Heap.prototype.pop = function() {
        let top = this.heap[0]
        this.heap[0] = this.heap[this.heap.length-1]
        this.heap.pop()
        this.sink(0)
        return top
    }
    /**
     * @param {number[][]} heightMap
     * @return {number}
     */
    var trapRainWater = function(heightMap) {
        if (!heightMap || !heightMap.length) {
            return 0
        }
        let m = heightMap.length
        let n = heightMap[0].length
        
        let marked = Array(m)
        let minHeap = new Heap((v1, v2) => v2[2] < v1[2])
        for (let i=0; i<m; i++) {
            marked[i] = Array(n).fill(false)
            for (let j=0; j<n; j++) {
                if (i===0 || j === 0 || i === m-1 || j=== n-1) {
                    minHeap.push([i, j, heightMap[i][j]])
                    marked[i][j] = true
                } 
            }
        }
        // console.log(minHeap.heap, marked)
        let res = 0
        let dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        while (minHeap.size()) {
            let c = minHeap.pop()
            for (let d of dirs) {
                dx = c[0] + d[0]
                dy = c[1] + d[1]
                if (dx>=0 && dx<m && dy>=0 && dy<n && !marked[dx][dy]) {
                    marked[dx][dy] = true
                    res += Math.max(0, c[2] - heightMap[dx][dy])
                    minHeap.push([dx, dy, Math.max(c[2], heightMap[dx][dy])])
                }
            }
        }
        
        return res;
        
    };
    

    At last, Thanks to all previous contributors.


Log in to reply
 

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