128. Longest Consecutive Sequence

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
    # time O(N) space O(N)
    # step1: create a hashset and put num into set
    # step2: loop through nums, check each num's neighbour if left neighbour not in the set(means num may be beginning of the sequence)
    # step3: create a experimental right neighbour and check if  right neighbour in the set.  if yes, increment right neighbour by one (extend the candidate sequence )keep while loop, record the count
    # step4: loop until  experimental right neighbour not in the set, exit while loop, update max_count
    # repeat step2 -4 until iteration of nums is over, return max_cnt
        _set = set(nums)
        max_cnt = 0
        for x in nums:
            if x-1 not in _set:
                y = x+1
                cnt = 1
                while y in _set:
                    cnt +=1
                    y +=1
                max_cnt = max(max_cnt,cnt) #  max(max_cnt, y-x), if want to ignore y 
        return max_cnt

class UF:
    def __init__(self,n):
        self.parent = list(range(n))
        self.ranks = [1]*n
        
    def find(self,x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self,u,v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.ranks[pu] < self.ranks[pv]:
            self.parent[pu] = pv
            self.ranks[pv] += self.ranks[pu]
        else:
            self.parent[pv] = pu
            self.ranks[pu] += self.ranks[pv]
        return True

class Solution:
# time O(N+MlogN)~ O(N)   space O(N)
    def longestConsecutive(self, nums: List[int]) -> int:
        n = len(nums)
        uf = UF(n)
        res= 0
        dic = {nums[i]:i for i in range(n)}
        for x in nums:
            if x-1  in dic:
                uf.union(dic[x],dic[x-1])
            if x+1 in dic:
                uf.union(dic[x],dic[x+1])
            px = uf.find(dic[x])
            res = max(res,uf.ranks[px])
        return res