[LC 128] Longest Consecutive Sequence

LeetCode 128

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.

This can be easily solved if we could sort the input first. But we need to solve this in linear time.

So let’s consider using a HashSet, and basically, check if the next consecutive number exists in the HashSet (constant lookup time). But what if the number has consecutive numbers on both sides? We will limit it so that we only start counting when we know it’s the first number of the sequence.

Saving the input on the HashSet gives us O(n) time. Because we only loop through the consecutive numbers if it’s the first number of the sequence, we will loop through the entire array only once, giving us a time complexity of O(n) as well.

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        exists = set(nums)  # O(n)
        maxlen = curlen = 0
        
        for num in nums:
            if num - 1 not in exists:   # first in sequence
                curlen = 1
                newnum = num + 1
                while newnum in exists:
                    curlen += 1
                    newnum += 1
                maxlen = max(maxlen, curlen)
                    
        return maxlen

Time: O(n)
Space: O(n)