# My Java Solution using UnionFound

• ``````public class Solution {
public int longestConsecutive(int[] nums) {
UF uf = new UF(nums.length);
Map<Integer,Integer> map = new HashMap<Integer,Integer>(); // <value,index>
for(int i=0; i<nums.length; i++){
if(map.containsKey(nums[i])){
continue;
}
map.put(nums[i],i);
if(map.containsKey(nums[i]+1)){
uf.union(i,map.get(nums[i]+1));
}
if(map.containsKey(nums[i]-1)){
uf.union(i,map.get(nums[i]-1));
}
}
return uf.maxUnion();
}
}

class UF{
private int[] list;
public UF(int n){
list = new int[n];
for(int i=0; i<n; i++){
list[i] = i;
}
}

private int root(int i){
while(i!=list[i]){
list[i] = list[list[i]];
i = list[i];
}
return i;
}

public boolean connected(int i, int j){
return root(i) == root(j);
}

public void union(int p, int q){
int i = root(p);
int j = root(q);
list[i] = j;
}

// returns the maxium size of union
public int maxUnion(){ // O(n)
int[] count = new int[list.length];
int max = 0;
for(int i=0; i<list.length; i++){
count[root(i)] ++;
max = Math.max(max, count[root(i)]);
}
return max;
}
}``````

• Very good idea! But I think the complexity of union-find is o(nlogn), right?

• I implemented the following code which is a slight improvement over the one suggested in the original post. I have optimized the retrieval of the `maxUnion` (`getHighestRank` in my case) to `O(1)`.

Also, @liangyue268 Weighted Union Find with Path Compression isn't exactly `O(nlogn)` but more close to `O(n)`. This is because the path compression function (see `find` operation) exhibits growth which follows the Inverse Ackermann Function. Both `union` and `find` are not exactly `1` but are very very very close to `1`, visit here for more details.

``````import java.util.Map;
import java.util.HashMap;

public class Solution {
public int longestConsecutive(int[] nums) {
final int length = nums.length;
if (length <= 1) return length;

final Map<Integer, Integer> elementIndexMap = new HashMap();
final UnionFind uf = new UnionFind(length);
for (int p = 0; p < length; p++) {
final int i = nums[p];
if (elementIndexMap.containsKey(i)) continue;
if (elementIndexMap.containsKey(i+1)) uf.union(p, elementIndexMap.get(i+1));
if (elementIndexMap.containsKey(i-1)) uf.union(p, elementIndexMap.get(i-1));
elementIndexMap.put(i, p);
}
return uf.getHighestRank();
}

private final class UnionFind {
final private int[] sequenceTree;
final private int[] rank;
private int highestRank;

UnionFind(int length) {
sequenceTree = new int[length];
rank = new int[length];
highestRank = 1;
for (int i = 0; i < length; i++) {
sequenceTree[i] = i;
rank[i] = 1;
}
}

void union(int p, int q) {
final int pId = find(p); final int qId = find(q);

if (pId == qId) return;

int localHighestRank = 1;
if (rank[pId] < rank[qId]) {
sequenceTree[pId] = qId;
rank[qId] += rank[pId];
localHighestRank = rank[qId];
} else {
sequenceTree[qId] = pId;
rank[pId] += rank[qId];
localHighestRank = rank[pId];
}
highestRank = Math.max(highestRank, localHighestRank);
}

int find(int p) {
while (p != sequenceTree[p]) {
sequenceTree[p] = sequenceTree[sequenceTree[p]];
p = sequenceTree[p];
}
return p;
}

int getHighestRank() { return highestRank; }
}
}
``````

• My Union find code from Princeton Algo. class

``````class Union_Find{
public:
Union_Find (int N) {
for (int i = 0; i < N; i++) {
id.push_back(i);
sz.push_back(1);
}
}

void Union(int A, int B) {
int rootA = Find(A);
int rootB = Find(B);
if (rootA == rootB) return;
if (sz[rootA] < sz[rootB]) {
id[rootA] = rootB;
sz[rootB] += sz[rootA];
} else {
id[rootB] = rootA;
sz[rootA] += sz[rootB];
}
}

int Find(int p) {
while (p != id[p]) {
id[p] = id[id[p]];
p = id[p];
}
return p;
}

int maxSize() {
int res = 0;
for (auto s : sz)
res = max(res, s);
return res;
}

private:
vector<int> id;
vector<int> sz;
};

class Solution {
public:
int longestConsecutive(vector<int>& nums) {
Union_Find uf(nums.size());
unordered_map<int, int> mapIndex;
for (int i = 0; i < nums.size(); i++) {
if (mapIndex.count(nums[i])) continue; // in case of duplicate
mapIndex.insert(make_pair(nums[i], i));

if (mapIndex.count(nums[i] + 1)) {
uf.Union(i, mapIndex[nums[i] + 1]);
}
if (mapIndex.count(nums[i] - 1)) {
uf.Union(i, mapIndex[nums[i] - 1]);
}
}
return uf.maxSize();
}
};
``````

• @liangyue268
More precisely, the UF algorithm with path compression and ranked union is `O(N+M log*N)`, where `M` is the number of UF operations (union and find), `N` is number of objects. `log*N` is a very slow growing function, which can be regarded as constant.

But the solution posted does not apply the ranked union mechanism, which makes its complexity be `O(MlogN)`. And for the problem, `M = O(N)`, thus the posted solution's complexity is `O(NlogN)`. Yeah, you are right :)

Reference: Princeton lecture notes, page 31 https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf

• ``````public int longestConsecutive2(int[] nums) {
int n = nums.length;
UnionFind uf = new UnionFind(n);

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) map.put(nums[i], i);

for (int num : nums)
if (map.containsKey(num+1))
uf.union(map.get(num), map.get(num+1));

return uf.getMaxSize();
}

private class UnionFind {
private int[] id;
private int[] sz;
private int maxSize;

public UnionFind(int n) {
id = new int[n];
sz = new int[n];
for (int i = 0; i < n; i++) {
id[i] = i;
sz[i] = 1;
}
maxSize = n > 0 ? 1 : 0;
}

public int findRoot(int i) {
if (i == id[i])  return i;
id[i] = findRoot(id[i]);
return id[i];
}

public void union(int p, int q) {
int rootP = findRoot(p);
int rootQ = findRoot(q);

if (rootP == rootQ)  return;
if (sz[rootP] < sz[rootQ]) {
id[rootP] = rootQ;
sz[rootQ] += sz[rootP];
maxSize = Math.max(maxSize, sz[rootQ]);
} else {
id[rootQ] = rootP;
sz[rootP] += sz[rootQ];
maxSize = Math.max(maxSize, sz[rootP]);
}
}

public int getMaxSize() {
return this.maxSize;
}
}``````

• `O(log*N)` is basically considered as constant. For Union and Find, if you do path compression, you will have O(log*N), so this solution is indeed O(n).

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