LeetCode 128: Longest Consecutive Sequence

Union-Find

We can consider an undirected graph where the distinct numbers are the vertices and an edge between two distinct vertices u and v exists if u = v-1 or u = v+1. The largest connected component of this number graph will have the longest path having consecutive numbers. Using Union-Find we can determine the largest connected component.

Say there are $n$ numbers with $m$ of them distinct.

Time: $\mathcal{O}(n \cdot \lg^*{n})$ , space: $\mathcal{O}(m)$ .

class UnionFind:
    def __init__(self, S):
        self.parent_of, self.rank_of = {}, {}
        self.component_count = 0
        for u in S:
            self.parent_of[u] = u
            self.rank_of[u] = 0
            self.component_count += 1

    def __compress_path(self, u, root):
        while u != (p := self.parent_of[u]):
            self.parent_of[u] = root
            u = p
    
    def __find(self, u):
        root = u
        while root != (p := self.parent_of[root]):
            root = p
        self.__compress_path(u, root)

        return root

    def connect(self, u, v):
        root_u = self.__find(u)
        root_v = self.__find(v)
        if root_u == root_v:
            return

        self.component_count -= 1
        
        rank_u = self.rank_of[root_u]
        rank_v = self.rank_of[root_v]
        if rank_u == rank_v:
            self.parent_of[root_u] = root_v
            self.rank_of[root_v] += 1
            return
        
        if rank_u > rank_v:
            self.parent_of[root_v] = root_u
        else:
            self.parent_of[root_u] = root_v

    def largest_cc_len(self):
        if self.component_count == 0:
            return 0

        cc_size = {}
        for u in self.parent_of:
            root_u = self.__find(u)
            cc_size[root_u] = cc_size.get(root_u, 0) + 1
        
        return max(cc_size.values())

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        uf = UnionFind(num_set)
        for y in nums:
            x = y-1
            z = y+1
            if x in num_set:
                uf.connect(x, y)
            if z in num_set:
                uf.connect(y, z)
        
        return uf.largest_cc_len()

Find sequence from a number

For a number $y$ , we can visit forward (y += 1) and backward (y -= 1) to find the sequence of consecutive numbers including y. To avoid duplicate computation, once a number is included in a sequence, we remove it from the set of available numbers.

Each number is visited at most twice, so time: $\mathcal{O}(n)$ , space: $\mathcal{O}(m)$ .

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        max_len = 0
        for y in nums:
            if y not in num_set:
                continue
            
            seq_len = 1
            
            z = y + 1
            while z in num_set:
                seq_len += 1
                num_set.remove(z)
                z += 1

            x = y - 1
            while x in num_set:
                seq_len += 1
                num_set.remove(x)
                x -= 1

            max_len = max(max_len, seq_len)
            num_set.remove(y)

        return max_len

unreasonably effective