# 200. Number of Islands

## Union-Find

In this solution, we use Weighted Quick-Union to count the number of connected domain, which is an implementation of Union-Find algorithm in Robert Sedgewick and Kevin Wayne’s Algorithm.

Note that we should minus the number of ‘0’ islands, cause the algorithm also considers them as independent connected domains.

class Solution {
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid.length == 0) {
return 0;
}
int row = grid.length;
int column = grid.length;
UnionFind uf = new UnionFind(row * column);
int zeroCounter = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {
if (grid[i][j] == '0') {
zeroCounter++;
continue;
}
int curr = i * column + j;
int target;
if (i > 0 && grid[i - 1][j] == '1') {
target = curr - column;
uf.union(curr, target);
}
if (i < row - 1 && grid[i + 1][j] == '1') {
target = curr + column;
uf.union(curr, target);
}
if (j > 0 && grid[i][j - 1] == '1') {
target = curr - 1;
uf.union(curr, target);
}
if (j < column - 1 && grid[i][j + 1] == '1') {
target = curr + 1;
uf.union(curr, target);
}
}
}
// remove '0' counting
return uf.count() - zeroCounter;
}

private static class UnionFind {
private int[] id;
private int[] sz;
private int count;

public UnionFind(int n) {
this.id = new int[n];
this.sz = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
sz[i] = 1;
}
this.count = n;
}

public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j) {
return;
}
// link small tree to large tree
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}
count--;
}

// find the root of p
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;
}
}
}


## DFS

class Solution {
public int numIslands(char[][] grid) {
if (grid.length == 0 || grid.length == 0) {
return 0;
}
int m = grid.length;
int n = grid.length;
int islands = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
// for all UNVISITED land, do a dfs
dfs(i, j, grid);
islands++;
}
}
}
return islands;
}

private void dfs(int i, int j, char[][] grid) {
// if (i, j) is out of bounds or (i, j) is not a land, return
if (i < 0 || j < 0 || i >= grid.length || j >= grid.length || grid[i][j] != '1') {
return;
}
// mark as visited
grid[i][j] = '0';
dfs(i - 1, j, grid);
dfs(i + 1, j, grid);
dfs(i, j - 1, grid);
dfs(i, j + 1, grid);
}
}