# 14ms Java Solution using Union Find with path compression and weight balancing

• `````` public class Solution {
public int find(int[] father, int id) {
int tf = father[id];
while (tf != father[tf]) tf = father[tf];
int cur = id, tmp;
while (father[cur] != tf) {
tmp = father[cur];
father[cur] = tf;
cur = tmp;
}
return tf;
}
public void union(int[] father, int[] sz, int id1, int id2) {
int tf1 = find(father, id1);
int tf2 = find(father, id2);
if (tf1 != tf2) {
if (sz[tf1] > sz[tf2]) {
father[tf2] = tf1;
sz[tf1] += sz[tf2];
}
else {
father[tf1] = tf2;
sz[tf2] += sz[tf1];
}
}
}
public List<Integer> numIslands2(int m, int n, int[][] positions) {
if (m == 0 || n == 0) return new ArrayList<Integer>();
ArrayList<Integer> res = new ArrayList<Integer>();
int[] father = new int[m * n];
for (int i = 0; i < father.length; i ++) father[i] = -1;
int[] sz = new int[m * n];
int[] dr = {0, 0, -1, 1};
int[] dc = {-1, 1, 0, 0};
int r, c, nr, nc, count = 0;
for (int i = 0; i < positions.length; i ++) {
r = positions[i][0];
c = positions[i][1];
count ++;
father[r * n + c] = r * n + c;
sz[r * n + c] = 1;
for (int j = 0; j < 4; j ++) {
nr = r + dr[j];
nc = c + dc[j];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && father[nr * n + nc] != -1) {
if (find(father, r * n + c) != find(father, nr * n + nc)) {
count --;
union(father, sz, r * n + c, nr * n + nc);
}
}
}