share my union find solution O(n) + O(n). Easily understood for begine

• ``````class UnionFind
{
private:
unordered_map<int, int> father;
unordered_map<int, int> ssize;

public:
int find(int x)
{
int parent = x;
while(parent != father[parent]) parent = father[parent];
int bigdaddy = parent;

while(x != father[x])
{
int tmp = father[x];
father[x] = bigdaddy;
x = tmp;
}
return bigdaddy;
}

void union_(int a, int b)
{
int fa = find(a);
int fb = find(b);
if (fa != fb)
{
father[fa] = fb;
ssize[fa] = ssize[fb] = ssize[fa] + ssize[fb];
}
}

UnionFind(vector<int> &nums)
{
for (int i = 0; i < nums.size(); i++)
{
father[nums[i]] = nums[i];
ssize[nums[i]] = 1;
}
}

int getmaxsize()
{
int result = 0;
for (auto it : ssize) result = max(result, it.second);
return result;
}

};

class Solution
{
public:
int longestConsecutive(vector<int>& nums)
{
UnionFind uf = UnionFind(nums);
unordered_set<int> s;
for (int i = 0; i < nums.size(); i++) s.insert(nums[i]);

for (int i = 0; i < nums.size(); i++)
{
if (s.count(nums[i] - 1)) uf.union_(nums[i], nums[i] - 1);
if (s.count(nums[i] + 1)) uf.union_(nums[i] + 1, nums[i]);
}
return uf.getmaxsize();
}
};
``````

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