Longest Consecutive Sequence

Given an array of integers nums, return the length of the longest consecutive sequence of elements that can be formed.

A consecutive sequence is a sequence of elements in which each element is exactly 1 greater than the previous element. The elements do not have to be consecutive in the original array.

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

The longest consecutive sequence is [2, 3, 4, 5].

Approach

Insert all numbers into a set, then only start counting from numbers that are the beginning of a sequence (i.e., num - 1 is not in the set). From each start, extend forward while the next number exists in the set, tracking the longest length. This naturally handles duplicates and the empty-array case.

Why It Works

Every consecutive sequence has exactly one starting number: the smallest element in that sequence. By only expanding from starts, each sequence is counted once, and the length computed is exact. Taking the maximum across all starts yields the correct longest consecutive length.

Complexity

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

Reference Implementation (Python)

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

        for num in num_set:
            if num - 1 not in num_set:
                current = num
                length = 1
                while current + 1 in num_set:
                    current += 1
                    length += 1
                if length > longest:
                    longest = length

        return longest