leetcode-study/longest-consecutive-sequence/ppxyn1.py at 2d4f7c22f8bbb09d1ebef9874ca35d55ce65c734 · DaleStudy/leetcode-study · 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
# idea: Hash
class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0

        num_set = set(nums)
        max_len = 1

        for num in num_set:
            if num - 1 not in num_set:
                current = num
                tmp = 1
                while current + 1 in num_set:
                    current += 1
                    tmp += 1
                if tmp > max_len:
                    max_len = tmp
        return max_len


'''
Trial and error

The code below was passed on Leecode since their Constraints was 0 <= nums.length <= 10^5.
But I realised that I missed another constraint they mentioned, which is "You must write an algorithm that runs in O(n) time."
'''
# class Solution:
#     def longestConsecutive(self, nums: List[int]) -> int:
#         if len(nums)==0:
#             return 0
#         sorted_nums = sorted(list(set(nums)))
#         # sorted_nums = sorted(nums) # duplicate
#         max_len = 1
#         tmp = 1

#         for i in range(1, len(sorted_nums)):
#             if sorted_nums[i] == sorted_nums[i - 1] + 1:
#                 tmp += 1
#             else:
#                 max_len = max(max_len, tmp)
#                 tmp = 1
#         ans = max(max_len, tmp)
#         return  ans