# Union find with weighted tree and path compression

• ``````public class Solution {
public int numIslands(char[][] grid) {
if(grid.length==0) return 0;
int m =grid.length;
int n=grid[0].length;
int [] arr = new int[m*n];
Arrays.fill(arr,-1);
int[] size =new int[m*n];
Arrays.fill(size,1);
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(grid[i][j]=='0'||arr[i*n+j]!=-1) continue;
arr[i*n+j]=i*n+j;
if(i>0&&grid[i-1][j]=='1')
union(arr,size,i*n+j,(i-1)*n+j);
// if(i<m-1&&grid[i+1][j]=='1')
//     union(arr,i*n+j,(i+1)*n+j);
if(j>0&&grid[i][j-1]=='1')
union(arr,size,i*n+j,i*n+(j-1));
// if(j<n-1&&grid[i][j+1]=='1')
//     union(arr,i*n+j,i*n+(j+1));
}
}
int isLandCount=0;
for(int i=0 ; i<arr.length;i++)
{
if(arr[i]==i)
isLandCount++;
}
return isLandCount;
}

public int root(int[] arr, int i)
{
while(arr[i]!=i)
{
arr[i]=arr[arr[i]];  // path compression
i=arr[i];
}
return i;
}
public void union(int[] arr ,int[] size, int i, int j)
{
int r1 = root(arr,i);
int r2 =root(arr,j);
if(r1==r2)return;
if(size[r1]<size[r2])    //weighted tree
{
arr[r1]=r2;
size[r2]+=size[r1];
}
else{
arr[r2]=r1;
size[r1]+=size[r2];
}
}
}
``````

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