200. Number of Islands using DSU

num_islands.js

/*

Approach:
- Use DSU
- For each cell, check if the one above, below, left or right is a 1. If they are, perform union.
- Remember to perform union on itself in case you have an orphan island.
- To create a unique identifier per cell, take the current row and multiply it by number of columns (3 for example), then add the current column. So the first row would be 0 * 3 (always 0), then add 0, 1, 2. Second row would be 1 * 3, then add 0, 1, 2… 

var x = current_row * num_columns + current_column

*/


var numIslands = function(rows) {
    if((rows==null)||(rows.length==0)) {
        return 0;
    }
    var d = new DSU();
    var num_col = rows[0].length;
    for(var r=0; r<rows.length; r++) {
        for(var c=0; c<rows[r].length; c++) {
            if(rows[r][c]=="1") {
                var x = r * num_col + c; //unique identifier
                // check one to the left
                if((rows[r][c-1])&&(rows[r][c-1]=="1")) {
                    var y = r * num_col + (c-1);
                    d.union(x,y);
                }
                // check one to the right
                if((rows[r][c+1])&&(rows[r][c+1]=="1")) {
                    var y = r * num_col + (c+1);
                    d.union(x,y);
                }
                // check one above
                if((rows[r-1])&&(rows[r-1][c])&&(rows[r-1][c]=="1")) {
                    var y = (r-1) * num_col + c;
                    d.union(x,y);
                }
                // check one below
                if((rows[r+1])&&(rows[r+1][c])&&(rows[r+1][c]=="1")) {
                    var y = (r+1) * num_col + c;
                    d.union(x,y);
                }
                //ensure orphan islands are still added
                d.union(x,x);
            }
        }
    }
    return d.getNumIslands();
};
    
    
class DSU {
	constructor() {
		this.parents = [];
	}
	find(x) {
		if(typeof this.parents[x] != "undefined") {
			if(this.parents[x]<0) {
				return x; //x is a parent
			} else {
				//recurse until you find x's parent
				return this.find(this.parents[x]);
			}
		} else {
			// initialize this node to it's on parent (-1)
			this.parents[x]=-1;
			return x; //return the index of the parent
		}
	}
	union(x,y) {
		var xpar = this.find(x);
		var ypar = this.find(y);
		if(xpar != ypar) {
			// x's parent is now the parent of y also. 
			// if y was a parent to more than one node, then
			// all of those nodes are now also connected to x's parent.
			this.parents[xpar]+=this.parents[ypar]; 
			this.parents[ypar]=xpar;
			return false;
		} else {
			return true; //this link creates a cycle
		}
	}
	getNumIslands() {
                var islands = 0;
		for(var i in this.parents) {
			var par = this.find(this.parents[i]);
                        if(par<0)
                        islands++;
	   	}
                return islands;
	}
}