# Simple UnionFind Java solution. Beat 75%

• There are many short excellent solutions for this particular problem. However, this problem can also be solved by union find. There is a very good material to learn union find.

https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

``````public class Solution {
int[] id;
int[] sz;
Map<Integer, Integer> map;

public int longestConsecutive(int[] nums) {
id = new int[nums.length];
sz = new int[nums.length];
map = new HashMap<>();

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

int res = 0;
for (int i = 0; i < nums.length; i++) {
res = Math.max(res, sz[i]);
}

return res;
}

private void insert(int num, int index) {
if (!map.containsKey(num)) {
map.put(num, index);
id[index] = index;
sz[index] = 1;
if (map.containsKey(num - 1)) {
unite(num - 1, num);
}
if (map.containsKey(num + 1)) {
unite(num + 1, num);
}
}
}

private void unite(int num1, int num2) {
int p = findSet(map.get(num1));
int q = findSet(map.get(num2));
if (p != q) {
if (sz[p] > sz[q]) {
id[q] = p;
sz[p] += sz[q];
} else {
id[p] = q;
sz[q] += sz[p];
}
}
}

private int findSet(int p) {
if (id[p] != p) {
id[p] = findSet(id[p]);
}
return id[p];
}
}
``````

• I understand that there are other solutions but it's very interesting to see other point of views! That was really helpful! Thanks :)

• @mehran thanks:)

• Nice solution.

But does it run in linear time complexity?

• No it's not linear complexity. If you read the slides I provided, it's (M + N) lg* N, where M union-find ops on a set of N objects

• @Rosti Although I think it's hard to prove lol

• @shuangling Thanks:)

• Can you get rid of the last loop by maintaining a max each time you update the sz array?

• @aval I think you can do so, using static variable? But I personally think having an extra loop is better to separate the logics:)

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