# Java, UnionFind with explanation

• I use union-find, union all water cells as a single component, union islands accordingly(follow the rules). For each island cell, only check its immediate right and down side if available.

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

int row = grid.length;
int col = grid[0].length;

// last extra cell is for water union
int[] uf = new int[row * col + 1];
// number of components at beginning, for each union, we minus one in count
int count = row * col + 1;
// init
for (int i = 0; i < uf.length; i++) { uf[i] = i; }

for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
// if water, connect it to last cell in uf[]
if (grid[i][j] == '0') { union(uf, i, j, row, 0, col); count--; }
else
{
// for eahc island, only check its down and right side if available
// check down side
if (i < row - 1 && grid[i + 1][j] != '0')
{
if (root(uf, i, j, col) != root(uf, i + 1, j, col))
{
union(uf, i, j, i + 1, j, col);
count--;
}
}
// check right side
if (j < col - 1 && grid[i][j + 1] != '0')
{
if (root(uf, i, j, col) != root(uf, i, j + 1, col))
{
union(uf, i, j, i, j + 1, col);
count--;
}
}
}
}
}
// exclude water part
return count - 1;
}

// have the same root?
private int root(int[] uf, int i, int j, int col)
{
int id = i * col + j;
while (uf[id] != id)
{
// compress path
uf[id] = uf[uf[id]];
id = uf[id];
}
return id;
}

// union these two
private void union(int[] uf, int i1, int j1, int i2, int j2, int col)
{
int r1 = root(uf, i1, j1, col);
int r2 = root(uf, i2, j2, col);
uf[r1] = r2;
}
}
``````

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