#128 Longest Consecutive Sequence

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class UnionFind:
    def __init__(self, n_size):
        self.root = [i for i in range(n_size)]
        self.size = [1 for i in range(n_size)]
        self.max_size = 1
    def find(self, x):
        while x != self.root[x]:
            x = self.root[x]
        return x
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.root[rootY] = rootX
            self.size[rootX] += self.size[rootY]
            if self.size[rootX] > self.max_size:
                self.max_size = self.size[rootX]
    def get_longest_sequence_size(self):
        return self.max_size



class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return len(nums)

        nums = list(set(nums))
        uf = UnionFind(len(nums))
        
        num_dict = dict()
        for i in range(len(nums)):
            if (nums[i] + 1) in num_dict:
                uf.union(num_dict[nums[i] + 1], i)
            if (nums[i] - 1) in num_dict:
                uf.union(num_dict[nums[i] - 1], i)
            num_dict[nums[i]] = i

        return uf.get_longest_sequence_size()