# Java Union Find Solution

• It's intuitive to come up with a union-find based solution. To make union-find algorithm more efficient, we use a weighted version of the algorithm and try to make the forest as flat as possible.

``````class Solution {
public int numIslands(char[][] grid) {
if (grid==null || grid.length<=0 || grid[0].length<=0) return 0;

int m = grid.length, n = grid[0].length;
int cnt = m*n, neighbor = 0, current = 0;

// Union-find data type
int[] uf = new int[cnt];
// Size for each island
int[] sz = new int[cnt];

// initiate each cell of land as separated
for (int i=0; i<cnt; i++) {uf[i]=i; sz[i]=1;}
for (int i=0; i<m; i++) {
for (int j=0; j<n; j++) {
if (grid[i][j]=='0') {cnt--; continue;}
// current: index for current cell in UnionFind array uf
current = i * n + j;
// Check cell above the current one
neighbor = (i - 1) * n + j;
if (i>0 && grid[i-1][j]=='1' && !connected(uf, current, neighbor)) {
union(uf, sz, current, neighbor);
cnt--;
}
// Check cell on the right hand side of the current one
neighbor = i * n + j + 1;
if (j<n-1 && grid[i][j+1]=='1' && !connected(uf, current, neighbor)) {
union(uf, sz, current, neighbor);
cnt--;
}
}
}
return cnt;
}

public void union(int[] uf, int[] sz, int i, int j) {
// make smaller trees point to larger ones
int ri = root(uf, i), rj = root(uf, j);
if (sz[ri] <= sz[rj]) {
uf[ri] = rj;
sz[rj] += sz[ri];
}
else {
uf[rj] = ri;
sz[ri] += sz[rj];
}
}

public int root(int[] uf, int i) {
// flat the tree by halve
while (i != uf[i]) {
uf[i] = uf[uf[i]];
i = uf[i];
}
return i;
}

public boolean connected(int[] uf, int i, int j) {
return root(uf, i) == root(uf, j);
}
}
``````

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