leetcode

Longest Consecutive Sequence

Longest Consecutive Sequence

O(n) Version - 40ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """    
        nums = set(nums)
        maxlen = 0
        while nums:
            first = last = nums.pop()
            while first - 1 in nums:
                first -= 1
                nums.remove(first)
            while last + 1 in nums:
                last += 1
                nums.remove(last)
            maxlen = max(maxlen, last - first + 1)
        return maxlen

O(n) Version - 44ms

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = set(nums)
        ret = 0
        for x in nums:
            if x - 1 not in nums:
                y = x + 1
                while y in nums:
                    y += 1
                ret = max(ret, y - x)
        return ret

test code

1
2
3
4
In [66]: s = Solution(); t = s.longestConsecutive([100, 4, 200, 3, 1, 2])
In [67]: t
Out[67]: 4

leet code