# Solution with union find algorithm

• Connect all water with one single end unit (m * n), and connect all land with its neighboring lands.

``````public class Solution {
public int numIslands(char[][] grid) {
int m = grid.length;
if(m <= 0) return 0;
int n = grid[0].length;
UF iUnion = new UF(m * n + 1);
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(grid[i][j] == '0') iUnion.connect(i * n + j, m * n);
else{
if(j < n - 1 && grid[i][j + 1] == '1') iUnion.connect(i * n + j, i * n + j + 1);
if(i < m - 1 && grid[i + 1][j] == '1') iUnion.connect(i * n + j, i * n + j + n);
}
}
}
return iUnion.size() - 1;
}

class UF{
private int[] weight;
private int[] uid;
private int size;
public UF(int capacity){
weight = new int[capacity];
uid = new int[capacity];
size = capacity;
for(int i = 0; i < capacity; i++){
uid[i] = i;
weight[i] = 1;
}
}

public int size(){
return size;
}

public int find(int p){
int start = p, tmp;
while(uid[p] != p){
p = uid[p];
}
// path compression
while(uid[start] != p){
tmp = uid[start];
uid[start] = p;
start = tmp;
}
return p;
}

public boolean connected(int p, int q){
return find(p) == find(q);
}

public void connect(int p, int q){
int pid = find(p);
int qid = find(q);
if(pid == qid) return;
if(weight[pid] > weight[qid]){
uid[qid] = pid;
weight[pid] += weight[qid];
}else{
uid[pid] = qid;
weight[qid] += weight[pid];
}
size--;
}
}
}``````

• If UF has a member method to decrease its size, there is no need to connect "water" to dummy node -- you can simply decrease size for a "water" grid.

Below is my Python solution using the same idea.

``````class DisjointSet(object):
def __init__(self, count):
# use list as parents and ranks
self.rank   = [0] * count
self.parent = range(count + 1)
self.size   = count

def find(self, x):
# path compression
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]]
x = self.parent[x]
return x

def union(self, x, y):
# union by rank
x, y = self.find(x), self.find(y)
if x != y:
self.size -= 1
if self.rank[x] > self.rank[y]:
self.parent[y] = x
else:
self.parent[x] = y
if self.rank[x] == self.rank[y]:
self.rank[y] += 1

class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
num_island, rows = 0, len(grid)
if rows > 0:
cols = len(grid[0])
ds = DisjointSet(rows*cols)
for x in xrange(rows):
for y in xrange(cols):
if grid[x][y] == '0':
# decrease size if current cell is water
ds.size -= 1
else:
# check and union with north / west cells if they are land
index = x*cols + y
if x-1 >= 0 and grid[x-1][y] == '1':
ds.union(index, index - cols)
y -= 1
if y >= 0 and grid[x][y] == '1':
ds.union(index, index-1)
num_island = ds.size

return num_island
``````

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