# Clean Java solution using union find

• The solution is inspired by the following tutorial of union find. Easy to implement:

Union-Find Algorithms

``````	class QuickUnion {
private int[] id;
private int[] size;
int m,n;
int island;

public QuickUnion(int m, int n) {
this.m = m;
this.n = n;
id = new int[m * n];
size = new int[m * n];
island = 0;
}

//Get the root for index i (root is the representative)
private int root(int i) {
while (i != id[i]) {
id[i] = id[id[i]];  //Path compression
i = id[i];
}
return i;
}

//Get the component size, if the size is 0 then we don't have an island yet.
public int getSize(int x, int y) {
return size[getIndex(x, y)];
}

private int getIndex(int x, int y) {
return x * n + y;
}

public void addIsland(int x, int y) {
int p = getIndex(x, y);
if (size[p] != 0) return;
size[p] = 1;
id[p] = p;
island++;
}

public void unite(int x1, int y1, int x2, int y2) {
unite(getIndex(x1, y1), getIndex(x2, y2));
}

private void unite(int p, int q) {
int i = root(p);
int j = root(q);
if (i != j) island--;  //If we are merging two different islands, then island count decreases.
if (size[i] < size[j]) {
id[i] = j;
size[j] += size[i];
}
else {
id[j] = i;
size[i] += size[j];
}
}
}

public List<Integer> numIslands2(int m, int n, int[][] positions) {
QuickUnion union = new QuickUnion(m,n);
int[] dx = {1,0,-1,0};
int[] dy = {0,1,0,-1};
List<Integer> result = new ArrayList<Integer>();
for (int[] pos : positions) {
int x = pos[0];
int y = pos[1];
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (newX < 0 || newY < 0 || newX >= m || newY >= n) continue;
if (union.getSize(newX, newY) == 0) continue;
union.unite(x, y, newX, newY);
}