roadmap/arrays-hashing/Longest Consecutive Sequence

Longest Consecutive Sequence

HardGoogleAmazonFacebookBloomberg

Problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. Must run in O(n).

Intuition — the key insight

The O(n) constraint rules out sorting. Key insight: only start counting a sequence from its beginning. A number n is the start of a sequence if and only if (n-1) is NOT in the set. This avoids redundant counting — we only count each sequence once, from its true start.

Approach

1. Build a HashSet

Add all numbers to a set for O(1) lookup.

2. Only count from sequence starts

For each number n, check if (n-1) is in the set. If it IS, skip — we'll count this sequence when we reach its start. If it's NOT, n is a sequence start. Count upward (n+1, n+2...) while in set.

Complexity

Time

O(n)

Space

O(n)

Each number is visited at most twice — once when checking if it's a start, once when counting from a start. Total O(n).

Solution code

Python

def longestConsecutive(self, nums: List[int]) -> int:
    num_set = set(nums)
    best = 0
    
    for n in num_set:
        if n - 1 not in num_set:  # n is a sequence start
            length = 1
            while n + length in num_set:
                length += 1
            best = max(best, length)
    
    return best

Edge cases to remember

⚠Empty array: return 0

⚠All duplicates: sequence length 1

⚠Negative numbers work fine with HashSet

Hints

What pattern do you think this problem uses?