128. Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Solution

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        numbers = set(nums)
        maxseq = 0
        for num in nums:
            if num in numbers:
                currseq=1
                #check left, aka num-1
                l = num-1
                while l in numbers:
                    numbers.remove(l)
                    currseq+=1
                    l-=1
                #check right, aka num+1
                r = num+1
                while r in numbers:
                    numbers.remove(r)
                    currseq+=1
                    r+=1
                maxseq = max(maxseq,currseq)
        return maxseq

Time Complexity: O(n)

Space Complexity: O(n)

Explanation

In the first approach, which leverages the deletion of processed numbers to ensure linear time, we grab an element from nums and go left and right looking for all numbers which are members of the sequence. These found members are then deleted to avoid being re-processed.

In a second approach, we could only go right when we find a start of a sequence. This ensures that numbers are only processed once since there can only be one start of a sequence.