128. Longest Consecutive Sequence

128. Longest Consecutive Sequence

1. O(N Log(N)) Solution - mine

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        heapq.heapify(nums)
        ans, tmp = 0, []
        while nums:
            num = heapq.heappop(nums)
            if not tmp:
                tmp.append(num)
            else:
                if tmp[-1] == num:
                    continue
                elif tmp[-1] + 1 == num:
                    tmp.append(num)
                    ans = max(ans, len(tmp))
                else:
                    tmp = [num]
        ans = max(ans, len(tmp))
        return ans

 

2. O(N) Solution - optimal

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums = set(nums)
        table = {}
        maxval = 0
        for num in nums:
            x = table.get(num - 1, 0)
            y = table.get(num + 1, 0)
            val = x + y + 1
            table[num - x] = val
            table[num + y] = val
            maxval = max(maxval, val)
        return maxval