# My simple Union-Find solution

• The basic idea is the Union-Find approach. We assign a root number for each island, and use an array to record this number. For each input, we check its four neighbor cells. If the neighbor cell is an island, then we retrieve the root number of this island. If two neighbor cells belong to two different islands, then we union them and therefore the total number of islands will become one less.

``````public List<Integer> numIslands2(int m, int n, int[][] positions) {
//use an array to hold root number of each island
int[] roots = new int[m*n];
//initialize the array with -1, so we know non negative number is a root number
Arrays.fill(roots, -1);

int[] xOffset ={0, 0, 1, -1};
int[] yOffset = {1, -1, 0, 0};

List<Integer> result = new ArrayList<Integer>();

for(int[] position : positions){
//for each input cell, its initial root number is itself
roots[position[0]*n + position[1]] = position[0]*n + position[1];
//count variable is used to count the island in current matrix.
//firstly, we assume current input is an isolated island
int count = result.isEmpty()? 1 : result.get(result.size()-1) + 1;
//check neighbor cells
for(int i = 0; i < 4; i++){
int newX = xOffset[i] + position[0];
int newY = yOffset[i] + position[1];
//if we found one neighbor is a part of island
if(newX >= 0 && newX < m && newY >= 0 && newY < n && roots[newX * n + newY] != -1){
//get the root number of this island
int root1 = find(newX * n + newY, roots);
//get the root number of input island
int root2 = roots[position[0]*n + position[1]];
//if root1 and root2 are different, then we can connect two isolated island together,
// so the num of island - 1
if(root1 != root2) count--;
//update root number accordingly
roots[root1] = root2;
}
}
}

return result;
}

public int find(int target, int[] roots){
//found root
if(roots[target] == target) return target;
//searching for root and update the cell accordingly
roots[target] = find(roots[target], roots);
//return root number
return roots[target];
}``````

• I think this line

``````int count = result.isEmpty()? 1 : result.get(result.size()-1) + 1;
``````

can be replace with `count++;` if you move the initialization outside before the loop like this `int count = 0;`

• My c++ version got LTE ; (

• This explanation is pretty easy to understand. Thanks!

One little improvements could be to put `int root2 = roots[position[0]*n + position[1]];` before checking each neighbor cell:

``````//check neighbor cells
for (int i = 0; i < 4; i++) {
``````

like

``````    for (int[] position : positions) {
//for each input cell, its initial root number is itself
int inputRoot = roots[position[0] * n + position[1]] = position[0] * n + position[1];
//cnt variable is used to cnt the island in current matrix.
//firstly, we assume current input is an isolated island
int cnt = result.isEmpty() ? 1 : result.get(result.size() - 1) + 1;
//check neighbor cells

for (int i = 0; i < 4; i++){
int newX = xOffset[i] + position[0];
int newY = yOffset[i] + position[1];
//if we found one neighbor is a part of island
if (newX >= 0 && newX < m && newY >= 0 && newY < n && roots[newX * n + newY] != -1) {
//get the root number of this island
int rootOfNeighbor = find(newX * n + newY, roots);
//if rootOfNeighbor and inputRoot are different, then we can connect two isolated island together,
// so the num of island - 1
if (rootOfNeighbor != inputRoot) cnt--;
//update root number accordingly
roots[rootOfNeighbor] = inputRoot;
}
}
}
``````

``````    for (int[] position : positions) {
//for each input cell, its initial root number is itself
roots[position[0]*n + position[1]] = position[0]*n + position[1];
//count variable is used to count the island in current matrix.
//firstly, we assume current input is an isolated island
int count = result.isEmpty()? 1 : result.get(result.size()-1) + 1;
//check neighbor cells
for(int i = 0; i < 4; i++){
int newX = xOffset[i] + position[0];
int newY = yOffset[i] + position[1];
//if we found one neighbor is a part of island
if(newX >= 0 && newX < m && newY >= 0 && newY < n && roots[newX * n + newY] != -1){
//get the root number of this island
int root1 = find(newX * n + newY, roots);
//get the root number of input island
int root2 = roots[position[0]*n + position[1]];
//if root1 and root2 are different, then we can connect two isolated island together,
// so the num of island - 1
if(root1 != root2) count--;
//update root number accordingly
roots[root1] = root2;
}
}
}
``````

Since we only need to assign the root of the input island once when iterating over its four neighbor cells.

• Another improvement could be to replace

``````roots[target] = find(roots[target], roots);
//return root number
return roots[target];
``````

with

``````return find(roots[target], roots);
``````

in find() method

• This post is deleted!

• @BryanBo.Cao The original way is intended, which set all the nodes along the path to directly point to the root. It makes the tree flat, known as path compression.

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