Problem Statement in English

You’re given an unsorted array of integers nums. Find the length of the longest consecutive elements sequence in $O(n)$ time complexity.

Approach

We can use a set to store all the numbers in the array.

Then, for each number, we check if it’s the start of a sequence (i.e., num - 1 is not in the set). This ensures that we don’t do repeated work, and can guarantee $O(n)$ time complexity.

If it is, we keep checking for the next consecutive numbers (num + 1, num + 2, etc.) and count the length of that sequence. We update our result with the maximum length found.

Solution in Python


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        s = set(nums)
        res = 0

        for x in s:
            if x - 1 in s:
                continue
            
            l = 1
            while x + l in s:
                l += 1
            
            res = max(res, l)

        return res

Complexity

  • Time: $O(n)$
    Since we iterate over the array once.

  • Space: $O(n)$
    Since we store all numbers in a set.

And we are done.