# JAVA, union find method, clean code with detailed comments

• ``````public class Solution {
/*
* Idea : Union Find
* If the new island does not connect any other existing islands, total islands increase 1
* If the new island connects x "different" islands together, total islands increase (i - x)
*
* Key: "different" root of an island differentiate it from other islands
*
* real performance: 15ms
* who can help me to calculate the time complexity? Thanks.
*/
private int[] array;
public List<Integer> numIslands2(int m, int n, int[][] positions) {
List<Integer> result = new ArrayList<>();
int len = m * n;
array = new int[len];
for (int i = 0; i < len; i ++) array[i] = i;
int[][] island = new int[m][n];
int num_island = 0;
for (int[] position : positions) {
int x = position[0];
int y = position[1];
int index = x * n + y;
int connect = 0;
int pos2 = x * n + y;
island[x][y] = 1;
if (x > 0 && island[x - 1][y] == 1) {
connect += helper(pos2 - n, pos2);
}
if (x < m - 1 && island[x + 1][y] == 1) {
connect += helper(pos2 + n, pos2);
}
if (y > 0 && island[x][y - 1] == 1) {
connect += helper(pos2 - 1, pos2);
}
if (y < n - 1 && island[x][y + 1] == 1) {
connect += helper(pos2 + 1, pos2);
}
num_island +=  1 - connect;
}
return result;
}

public int helper(int pos1, int pos2) {
int root = findRoot(pos1);
array[root] = pos2;
return root != pos2 ? 1 : 0;
}

public int findRoot(int pos) {
if (pos == array[pos]) {
return pos;
} else {
array[pos] = findRoot(array[pos]);
return array[pos];
}
}
}
``````

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