# union find weighted balancing path compression

• ``````public class Solution {
HashMap<Integer,Integer> map;
HashMap<Integer,Integer> size;
public int longestConsecutive(int[] nums) {
map = new HashMap<>();
size =new HashMap<>();
for(int num: nums)
{
if(map.containsKey(num)) continue;
map.put(num,num);
size.put(num,1);
if(map.containsKey(num-1))
union(num,num-1);
if(map.containsKey(num+1))
union(num,num+1);
}
int maxCount=0;
for(int val : size.values()) maxCount=Math.max(val,maxCount);
return maxCount;
}

public int root(int i)
{
while(map.get(i)!=i)
{
map.put(i,map.get(map.get(i)));
i=map.get(i);
}
return i;
}

public void union( int i ,int j)
{
if(i==j) return;
int root1=root(i);
int root2=root(j);
int size1=size.get(root1);
int size2 =size.get(root2);
if(size1<size2)
{
map.put(root1,root2);
size.put(root2,size1+size2);
}
else{
map.put(root2,root1);
size.put(root1,size1+size2);
}
}
}
``````

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