[LeetCode] 128. Longest Consecutive Sequence

Problem : https://leetcode.com/problems/longest-consecutive-sequence/

Hash table based solution:

Store the input numbers in Set. Then lookup for consecutive sequence if current number does not have preceding number.

Time Complexity = O ( N )

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

Union-Find based solution:

Put the contiguous numbers in one group. Then find the maximum number of items in one group.

class UnionFind:
    def __init__(self, nums):
        self.memo = {}
        for n in nums:
            self.memo[n] = n
    
    def union(self, x, y):
        parent = y
        while parent != self.memo[parent]:
            tmp = self.memo[parent]
            self.memo[parent] = self.memo[x]
            parent = tmp
            
        self.memo[y] = self.memo[x]
    
    def find(self, x):
        if x not in self.memo:
            return None
        
        parent = self.memo[x]
        
        while self.memo[parent] != parent:
            parent = self.memo[parent]
    
        while self.memo[x] != parent:
            tmp = self.memo[x]
            self.memo[x] = parent
            x = tmp
            
        return parent

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        uf = UnionFind(nums)
        
        for n in nums:
            if uf.find(n-1) != None:
                uf.union(n-1, n)
            
            if uf.find(n+1) != None:
                uf.union(n, n+1)
        
        maxLength  = defaultdict(int)
        
        # count number of items in each group
        for k in uf.memo.keys():
            p = uf.find(k)
            maxLength[p] += 1
        
        return max(maxLength.values()) if maxLength.values() else 0