<p>Given an unsorted array of integers <code>nums</code>, return <em>the length of the longest consecutive elements sequence.</em></p>

<p>You must write an algorithm that runs in&nbsp;<code>O(n)</code>&nbsp;time.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [100,4,200,1,3,2]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The longest consecutive elements sequence is <code>[1, 2, 3, 4]</code>. Therefore its length is 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [0,3,7,2,5,8,4,6,0,1]
<strong>Output:</strong> 9
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class UF:
    def __init__(self, nums):
        self.pa = {n:n for n in nums}
        self.ra = {n:1 for n in nums}
    def find(self, n):
        while self.pa[n] != n:
            self.pa[n] = self.pa[self.pa[n]]
            n = self.pa[n]
        return n
    def union(self, n1, n2):
        if n1 not in self.pa: return False
        if n2 not in self.pa: return False
        p1,p2 = self.find(n1), self.find(n2)
        if p1 == p2: return False
        if self.ra[p1] > self.ra[p2]:
            self.pa[p2] = p1
            self.ra[p1] += self.ra[p2]
        else:
            self.pa[p1] = p2
            self.ra[p2] += self.ra[p1]
        return True

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums: return 0
        uf = UF(nums)
        for n in nums:
            uf.union(n, n-1)
        return max(uf.ra.values())
40930