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

• ``````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);
}
}
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;
}
}
``````

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

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--;

}

``````

• 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.

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