Problem Description

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.

Example 1:

  • Input: nums = [100,4,200,1,3,2]
  • Output: 4
  • Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2:

  • Input: nums = [0,3,7,2,5,8,4,6,0,1]
  • Output: 9

My Idea

To find the longest sequence in O(n) time, we’d need to optimize the data structure for nums by converting in to a set, since set lookup happens ins constant time O(1). This way we can take any possible start of a sequence, check how long it is and in the end return the longest one.

My solution

def longestConsecutive(nums: list[int]) -> int:
    if nums==[]:
        return 0
    snums=set(nums)
    res=1
    for n in nums:
        if n-1 not in snums:
            curr=n+1
            while curr in snums:
                curr+=1
            res=max(res,curr-n)
    return res