LeetCode: 128. Longest Consecutive Sequence

O(N) 알고리즘.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        longest = 0
        nums = set(nums)
        for num in nums:
            if num - 1 not in nums:
                cnt = 1
                while num + 1 in nums:
                    num += 1
                    cnt += 1
                longest = max(longest, cnt)
        return longest

 

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numSet = set(nums)
        longest = 0
        while nums:
            cnt = 1
            l = r = nums.pop()
            numSet.discard(l)
            while l - 1 in numSet or r + 1 in numSet:
                if l - 1 in numSet:
                    numSet.discard(l-1)                    
                    cnt += 1
                    l -= 1
                if r + 1 in numSet:
                    numSet.discard(r+1)
                    cnt += 1
                    r += 1
            longest = max(longest, cnt)
        return longest