# Weighted Quick Union Find Path Compression - Java

• public class Solution {

``````public int numIslands(char[][] grid) {
//Corner case
if(grid == null || grid.length == 0) return 0;
if(grid[0] == null || grid[0].length == 0) return 0;

int row = grid.length;
int col = grid[0].length;
int size = row * col;

QuickFindPathComp qfpc = new QuickFindPathComp(size, grid);

for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
if(grid[i][j] == '1'){
int currIndex = i * col + j;
int upIndex = (i - 1) * col + j;
int downIndex = (i + 1) * col + j;
int leftIndex = i * col + (j - 1);
int rightIndex = i * col + (j + 1);

//up
if(i > 0 && grid[i-1][j] == '1'){
qfpc.union(currIndex, upIndex);
}

//down
if(i > row - 1 && grid[i+1][j] == '1'){
qfpc.union(currIndex, downIndex);
}

//left
if(j > 0 && grid[i][j - 1] == '1'){
qfpc.union(currIndex, leftIndex);
}

//right
if(j < col - 1 && grid[i][j + 1] == '1'){
qfpc.union(currIndex, rightIndex);
}
}
}
}
return qfpc.getCount();
}
``````

}

class QuickFindPathComp {
private int[] id;
private int[] sz;
private int count;

``````public QuickFindPathComp(int size, char[][] grid){
id = new int[size];
sz = new int[size];

//Initialize
for(int i = 0; i < size; i++){
id[i] = i;
sz[i] = 1; //each spot is an individual tree
}

//Counting how many spots are a land
for(int row = 0; row < grid.length; row++){
for(int col = 0; col < grid[0].length; col++){
if(grid[row][col] == '1'){
count++;
}
}
}
}

public int getCount(){
return count;
}

public int root(int p){
while(p != id[p]){
id[p] = id[id[p]]; // for path compression
p = id[p];
}
return p;
}

public void union(int p, int q){
int pId = root(p); //find p's current parent root
int qId = root(q); //find q's current parent root

//if p & q is connected then return
//Otherwise count - 1, because land p , q is connected with each others
if (pId == qId){
return;
}
count--;

// refactor the tree -> smaller tree should append into large tree
if(sz[pId] < sz[qId]){
id[pId] = id[qId];
sz[qId] += sz[pId];
}else{
id[qId] = id[pId];
sz[pId] += sz[qId];
}
}
``````

}

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