leetcode-solution/Python/0128-longest-consecutive-sequence.py at main · hogan-tech/leetcode-solution · GitHub

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
# time complexity: O(n^3)
# space complexity: O(1)
from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longestStreak = 0
        numSet = set(nums)

        for num in nums:
            if num - 1 not in numSet:
                currentNum = num
                currentStreak = 1

                while currentNum + 1 in numSet:
                    currentNum += 1
                    currentStreak += 1

                longestStreak = max(longestStreak, currentStreak)

        return longestStreak


# time complexity: O(n^2)
# space complexity: O(n)
class UnionFind:
    def __init__(self, nums):
        self.parents = {num: num for num in nums}
        self.ranks = {num: 1 for num in nums}
        self.maxLength = 1

    def find(self, num):
        if num != self.parents[num]:
            self.parents[num] = self.find(self.parents[num])
        return self.parents[num]

    def union(self, node1, node2):
        parent1 = self.find(node1)
        parent2 = self.find(node2)

        if parent1 == parent2:
            return False

        if self.ranks[parent1] < self.ranks[parent2]:
            self.parents[parent1] = parent2
            self.ranks[parent2] += self.ranks[parent1]
        else:
            self.parents[parent2] = parent1
            self.ranks[parent1] += self.ranks[parent2]

        self.maxLength = max(
            self.maxLength, self.ranks[parent1], self.ranks[parent2])

        return True


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        uf = UnionFind(nums)
        for num in nums:
            if num + 1 in uf.parents:
                uf.union(num, num + 1)

        return uf.maxLength

# time complexity: O(nlogn)
# space complexity: O(n)
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0

        nums.sort()

        longestStreak = 1
        currentStreak = 1

        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1]:
                if nums[i] == nums[i - 1] + 1:
                    currentStreak += 1
                else:
                    longestStreak = max(longestStreak, currentStreak)
                    currentStreak = 1

        return max(longestStreak, currentStreak)


nums = [100, 4, 200, 1, 3, 2]
print(Solution().longestConsecutive(nums))
nums = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
print(Solution().longestConsecutive(nums))
nums = [1, 0, 1, 2]
print(Solution().longestConsecutive(nums))