# Union-find by rank and path compression- with Explanation

• ``````public class Solution {
int[] parent;
int[] rank;
int numIslands;
public List<Integer> numIslands2(int m, int n, int[][] positions) {
if(m == 0 || n == 0)return new ArrayList<Integer>();

int k = positions.length;
if(k == 0) return new ArrayList<Integer>();

parent = new int[m*n];
rank = new int[m*n];
int[][] matrix = new int[m][n];

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

//set parent to itself
for(int i = 0; i< m*n ;i++){
parent[i] = i;
}

int[][] dirs = {{-1,0}, {1, 0}, {0, 1}, {0, -1}};
numIslands = 0;
//for each of the positions in positions
for(int[] position : positions){
numIslands++; // increment nums islands and decrement while doing union if necessary
int pos1 = n * position[0] + position[1];
matrix[position[0]][position[1]] = 1;

//check all four directions and check if there was an another island nearby and do union
for(int[] dir : dirs){
int row = position[0] + dir[0];
int col = position[1] + dir[1];

//validity check
if(row < 0 || col< 0 || col>=n || row >= m || matrix[row][col] != 1) continue;

int pos2 = n * row + col;
union(pos1, pos2);
}

}

return result;
}

private void union(int node1, int node2){
//union by rank
int parent1 = find(node1);
int parent2 = find(node2);

//important condition, if in same set skip union
if(parent1 == parent2) return;

//union
if(rank[parent1] < rank[parent2]){
parent[parent1] = parent2;
}else{
if(rank[parent1] == rank[parent2])
rank[parent1]++;
parent[parent2] = parent1;
}

numIslands--;
}

private int find(int node){
while(parent[node]!=node){
parent[node] = parent[parent[node]];
node = parent[node];
}
return node;
}
}
``````

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