Longest Consecutive Sequence

Problem: Longest Consecutive Sequence

We can use union-find to solve this problem. While scanning the numbers, once we get a new one, first we add it to our disjoint set, then we find its neighbors. If its neighbors are in sets, we do union them and update size of disjoint sets. Then we can return our answer from stored sizes.

Code in Python:

class Solution(object):
    def __init__(self):
        self.id = {}
        self.size = {}

    def union(self, x, y):
        def root(x):
            while self.id[x] != x:
                self.id[x] = self.id[self.id[x]]
                x = self.id[x]
            return self.id[x]
        rx, ry = root(x), root(y)
        if rx == ry: return
        if self.size[rx] < self.size[ry]: rx, ry = ry, rx
        self.id[ry] = rx
        self.size[rx] += self.size[ry]

    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for num in nums:
            if num not in self.id:
                self.id[num] = num
                self.size[num] = 1
            if num-1 in self.id: self.union(num, num-1)
            if num+1 in self.id: self.union(num, num+1)
        return max(self.size.values())

However, in this problem, actually we don't need skills like path compression. We can use a modified version of union-find to just keep numbers and sizes in a dictionary. The updated sizes are only needed in edge numbers. There's a tricky solution here.