Python3 | O(n) | Union-Find/Disjoint Set | Full explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nTo find longest consecutive sequence, for every integer num, we need to look for num - 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nTo find longest consecutive sequence, for every integer num, we need to look for num - 1 and num + 1. One of the ways of doing this is to use Union Find (or Disjoint Set) Data Structure.\n\nWe use this to combine all the consecutive elements and get the largest set.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize a union-find data structure with each element in the input vector as a separate disjoint set.\n\n2. Iterate through the elements in the input vector. For each element, check if the element before and after it (in consecutive order) exist in the union-find data structure. If they do, use the union function to merge their sets.\n\n3. After all elements have been processed, iterate through the sets in the union-find data structure and find the set with the largest size. The size of this set is the length of the longest consecutive sequence.\n\n\n# Complexity\n- Time complexity: O(n * \u03B1(n)) [where \u03B1(n) is the inverse Ackermann function]\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass UnionFind:\n    def __init__(self, size: int) -> None:\n        # Initially, all the elements will have themselves as the parent\n        self.parent = [i for i in range(size)]\n        # Which also means that their size will be 1\n        self.size = [1 for _ in range(size)]\n\n    def find(self, x: int) -> int:\n        # If the parent of the x is not itself, recursively find the parent\n        # And apply path compression by assigning the root as the parent\n        if self.parent[x] != x:\n            self.parent[x] = self.find(self.parent[x])\n        return self.parent[x]\n\n    def union(self, x: int, y: int) -> None:\n        # Find the roots of x and y\n        x_root = self.find(x)\n        y_root = self.find(y)\n\n        # If they both do not belong to the same set\n        if x_root != y_root:\n            # Check which one is smaller\n            # Smaller one should have the bigger one as parent\n            if self.size[x_root] < self.size[y_root]:\n                # x now has y as parent and y\'s size has increased by the size of x\n                self.parent[x_root] = y_root\n                self.size[y_root] += self.size[x_root]\n            else:\n                self.parent[y_root] = x_root\n                self.size[x_root] += self.size[y_root]\n\nclass Solution:\n    def longestConsecutive(self, nums: List[int]) -> int:\n        # Initialize UnionFind data structure for nums\n        uf = UnionFind(len(nums))\n        \n        # Initialize a dictionary to store the indices of all integers\n        index = dict()\n\n        for i, num in enumerate(nums):\n            # Ignore duplicates\n            if num in index:\n                continue\n\n            index[num] = i\n\n            # Perform union with num - 1 and num + 1, if seen\n            if num - 1 in index:\n                uf.union(i, index[num - 1])\n            if num + 1 in index:\n                uf.union(i, index[num + 1])\n\n        # Find the largest set (include [0] in case the input has no elements)\n        return max(uf.size + [0])\n```
['Array', 'Hash Table', 'Union Find', 'Python', 'Python3']