Share my union-find solution based on weighted quick-union (Runtime: 19 ms)


  • 1
    H
    public class Solution {
        public List<Integer> numIslands2(int m, int n, int[][] positions) {
            List<Integer> result = new ArrayList<Integer>();
            if (positions == null || positions.length == 0 || positions[0].length == 0) {
                return result;
            }
            UnionFind uf = new UnionFind(m * n);
            int[][] board = new int[m][n];
            for (int i = 0; i < positions.length; i++) {
                int x = positions[i][0];
                int y = positions[i][1];
                board[x][y] = 1;
                int p = x * n + y;
                if (x > 0 && board[x - 1][y] == 1) {
                    uf.union(p, p - n);
                }
                if (x < m - 1 && board[x + 1][y] == 1) {
                    uf.union(p, p + n);
                }
                if (y > 0 && board[x][y - 1] == 1) {
                    uf.union(p, p - 1);
                }
                if (y < n - 1 && board[x][y + 1] == 1) {
                    uf.union(p, p + 1);
                }
                result.add(i + 1 - uf.count());
            }
            return result;
        }
    }
    class UnionFind {
        private int[] id;
        private int[] size;
        private int count;
        public UnionFind(int n) {
            id = new int[n];
            size = new int[n];
            count = 0;
            for (int i = 0; i < n; i++) {
                id[i] = i;
                size[i] = 1;
            }
        }
        public void union(int p, int q) {
            int i = find(p);
            int j = find(q);
            if (i == j) {
                return;
            }
            if (size[i] < size[j]) {
                id[i] = j;
                size[j] += size[i];
            } else {
                id[j] = i;
                size[i] += size[j];
            }
            count++;
        }
        public int find(int p) {
            while (p != id[p]) {
                p = id[p];
            }
            return p;
        }
        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }
        public int count() {
            return count;
        }
    }
    

    Reference: Algorithms, 4th Edition Robert Sedgewick and Kevin Wayne


  • 0
    K

    Hi, in your solution for adding count in each position insertion:

    result.add(i + 1 + uf.count());

    could you please explain this line i + 1 + uf.count() ?

    The reason I ask is because I find count() returns the count of space that are not connected. Therefore, changing the line to Math.abs(i + 1 + uf.count() - m*n) returns the desired output for my solution in Javascript.

    var numIslands2 = function(m, n, positions) {
        var board = [];
        for(var i = 0; i < m; i++){
            board.push([]);
            for(var j = 0; j < n; j++){
                board[i][j] = 0;
            }
        }
        var count = 0;
        var res = [];
        var uf = new UnionFind(m * n);
        for(var k = 0; k < positions.length; k++){
          var pos = positions[k];
          var x = pos[0];
          var y = pos[1];
          board[x][y] = 1;
          var p = x * n + y;
         if(x > 0 && board[x-1][y] == 1){
         	uf.union(p, p-n);
         }
         if(x < m - 1 && board[x+1][y] == 1){
         	uf.union(p, p + n);
         }
         if(y > 0 && board[x][y-1] == 1){
         	uf.union(p, p -1);
         }
         if(y < n-1 && board[x][y+1] == 1){
         	uf.union(p, p+1);
         }
          res.push( Math.abs((k + 1 + uf.countNum()) - m*n));
        }
        
        return res;
        
    };
    
    function UnionFind(n){
    	this.count = n;
    	this.size = [];
    	this.parent = []; 
    	for(var i = 0; i < n; i++){
    		this.size[i] = i;
    		this.parent[i] = i;
    	}
    }
    
    UnionFind.prototype.countNum = function(){
    	return this.count;
    }
    
    UnionFind.prototype.connected = function(p, q){
    	return this.parent[p] == this.parent[q];
    }
    
    UnionFind.prototype.validate = function(p){
    	var n = this.parent.length;
    	if(p < 0 || p >= n){
    		return false;
    	}
    	return true
    }
    
    UnionFind.prototype.find = function(p){
    	var validated = this.validate(p);
    	if(validated){
    		while(p !== this.parent[p]){
    			p = this.parent[p];
    		}
    		return p;
    	}
    	return null;
    }
    UnionFind.prototype.union = function(p, q){
    
    	var parentP = this.find(p);
    	var parentQ = this.find(q);
    		if(parentP == parentQ) return;
    
    	if(this.size[parentP] < this.size[parentQ]){
    		this.parent[parentP] = parentQ;
    		this.size[parentQ] += this.size[parentP];
    	}
    	else{
    		this.parent[parentQ] = parentP;
    		this.size[parentP] += this.size[parentQ];
    	}
    	this.count--;
    	
    }
    
    

  • 0
    H

    Hi @karen7, thank you for asking. I have modified the code in my solution, it will be better for understanding this time:

    1. each time we call uf.union(int p, int q), we do count++, so when we call uf.count() it will return how many islands are already connected so far;
    2. each time when we got a position, let's say positions[i], after we mark an island in this position, it means we have marked i + 1 islands right now;
    3. then we can get how many disconnected islands are there in the matrix by calculating i + 1 - uf.count().

    In the original version, we do count-- when we call uf.union(int p, int q), so each time we got a negative number to represent how many islands are connected when we call uf.count(), which makes we need to use i + 1 + uf.count() to get how many disconnected islands are there.


Log in to reply
 

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