# TLE for union-find solution

• This is my union-find solution. I do compression on the findRoot() method, so I think the time complexity should be in O(n), but it got TLE. Anyone can help to improve the performance?

``````public class Solution {
public int longestConsecutive(int[] nums) {
Map<Integer, Integer> roots = new HashMap<Integer, Integer>();

for(int i = 0; i < nums.length; i++) {
roots.put(nums[i], nums[i]);
}

for(int item : roots.keySet()) {
if(roots.containsKey(item + 1)) {
roots.put(item, item + 1);
}
}

for(int item : roots.keySet()) {
findRoot(roots, item);
}

// aggregate by root
Map<Integer, Integer> unions = new HashMap<Integer, Integer>();
int max = -1;
for(int item : roots.keySet()) {
int unionId = roots.get(item);
if(!unions.containsKey(unionId)) {
unions.put(unionId, 1);
} else {
unions.put(unionId, unions.get(unionId) + 1);
}
max = Math.max(max, unions.get(unionId));
}

return max;
}

private void findRoot(Map<Integer, Integer> roots, int item) {
int cur = item;
while(item != roots.get(item)) {
item = roots.get(item);
}
roots.put(cur, item);
}
}
``````

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