Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        ans = 0
        
        for x in nums:
            # Find the first element in one segment
            if x-1 not in nums:
                y = x + 1
                # reach the last consecutive element in one element  
                while y in nums:
                    y += 1
                ans = max(ans, y - x)
             
        return ans

class Solution:
    def longestConsecutive(self, nums) -> int:
        UF = {}
        nums = set(nums)

        if not nums:
            return 0

        # for num in nums:
        #     UF[num] = num

        def find(x):
            if x != UF[x]:
                UF[x] = find(UF[x])
            return UF[x]

        def union(x, y):
            UF.setdefault(x, x)
            UF.setdefault(y, y)
            UF[find(x)] = find(y)

        for n in nums:
            if (n - 1) in nums:
                union(n - 1, n)
            if (n + 1) in nums:
                union(n, n + 1)

        ans = 1

        for num in nums:
            if num in UF:
                ans = max(ans, find(num) - num + 1)
        return ans