[link](https://leetcode.com/problems/longest-consecutive-sequence/)

---

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

You must write an algorithm that runs in O(n) time.

#### Example 1:

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

#### Example 2:

Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

#### Constraints:

- 0 <= nums.length <= 105
- -109 <= nums[i] <= 109

---

numSet: It creates a set numSet containing all the distinct elements from the input list nums. Using a set allows for faster lookups compared to lists.

Main algorithm: The algorithm iterates through each element n in the input list nums. For each n, it checks if n - 1 is not present in the set numSet. If n - 1 is not in the set, it means that n is the start of a potential consecutive subsequence.

If n - 1 is not in the set, the algorithm initiates a while loop. It increments a variable length starting from 1 and keeps checking if n + length is in the set numSet. If it is, it means the subsequence is continuing, so the length of the subsequence is incremented by 1. The loop continues until n + length is not present in the set, which means the consecutive subsequence has ended.

The algorithm keeps track of the longest subsequence length found so far in the variable longest. It updates longest if the current subsequence's length is greater than the previous longest subsequence length.

After iterating through all elements in nums, the algorithm returns the final value of longest, which represents the length of the longest consecutive subsequence.

#### Solution 1

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        longest = 0
        
        for n in numSet:
            if (n - 1) not in numSet:
                length = 1
                while (n + length) in numSet:
                    length += 1
                longest = max(length, longest)
        return longest

O(T): O(n)
O(S): O(n)

---

UnionFind class: This class is a union-find data structure, which is used to manage connected components. It initializes with a list of integers lst and sets up the parent and rank dictionaries (par and rank, respectively). Each element in lst is considered a separate connected component.

find method: The find method is a standard union-find operation that finds the representative element (parent) of a given element. It uses path compression to optimize the find operation.

union method: The union method is used to merge two connected components represented by n1 and n2. It finds the representatives of n1 and n2 using the find method and then merges the components based on their ranks.

longestConsecutive method: The main algorithm starts by creating a UnionFind instance uf with the elements in the nums list. It then iterates through each element n in the nums list. For each n, it checks if n - 1 and n + 1 are also present in nums.

If n - 1 is in nums, it means that there is a potential consecutive subsequence starting at n - 1, so it unifies n and n - 1 using the union method.

If n + 1 is in nums, it means that there is a potential consecutive subsequence starting at n, so it unifies n and n + 1 using the union method.

After the loop, the uf instance now contains connected components, where elements in the same connected component form consecutive subsequences. The algorithm creates a defaultdict d, which will store the connected components and their elements.

The algorithm iterates through the set of unique elements in nums. For each element n, it finds the representative of its connected component using the uf.find method and appends n to the corresponding component list in d.

Finally, the algorithm returns the length of the longest list in d, which corresponds to the length of the longest consecutive subsequence.

#### Solution 2

class UnionFind():
    def __init__(self, lst):
        self.par = {}
        self.rank = {}

        for num in lst:
            self.par[num] = num
            self.rank[num] = 0


    def find(self, x):
        while x != self.par[x]:
            self.par[x] = self.find(self.par[x])
            x = self.par[x]
        return x


    def union(self, n1, n2):
        p1, p2 = self.find(n1), self.find(n2)
        if p1 != p2:
            if self.rank[p1] >= self.rank[p2]:
                self.par[p2] = p1
                self.rank[p1] += 1
            else:
                self.par[p1] = p2
                self.rank[p2] += 1


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0

        uf = UnionFind(nums)
        for n in nums:
            if (n - 1) in nums:
                uf.union(n, n - 1)
            if (n + 1) in nums:
                uf.union(n, n + 1)
        d = collections.defaultdict(list)
        for n in set(nums):
            d[uf.find(n)].append(n)
        return max([len(v) for v in d.values()])

The time complexity of the algorithm depends on the time complexity of the UnionFind operations, which is typically O(log n) per operation with path compression and union by rank. The overall time complexity of the algorithm is O(n log n), where n is the number of elements in the input list nums.

The space complexity is O(n), mainly due to the storage of elements in the UnionFind instance and the d dictionary.