Longest Consecutive Sequence

Longest Consecutive Sequence looks like a sorting problem, but the trick is to solve it in O(n) with a hash set — and to be clever about which numbers you start counting from.

The slow way first

The obvious idea is to sort the array, then sweep through it counting consecutive runs. That works, but sorting is O(n log n) — and the problem explicitly asks for O(n). We need to find runs without ordering everything.

The question to ask: while I am looking at one number, what do I wish I could check instantly? I wish I could ask "is num + 1 also here?" — and a hash set answers that in O(1).

The idea: only count from a run's start

Dump every number into a set. Now, for each number, I could walk num + 1, num + 2, … counting how far the run goes. But if I did that for every number, I would re-walk the same run over and over — that is O(n²).

The fix: only start walking when num is the beginning of a run. A number num begins a run exactly when num - 1 is not in the set. Then I walk forward from there. Because each number is the start of at most one run, the total walking is O(n).

The key insight: the num - 1 not in set guard is what keeps it O(n). It guarantees we only ever walk a run from its leftmost element, so no number is counted twice.

Walk through it

Step through the animation. 100 and 200 are lonely starts (length 1). 4 is skipped because 3 sits before it — it is not a start. When the pointer reaches 1 (since 0 is absent, 1 is a start), we walk 1 → 2 → 3 → 4, lighting up the whole run, until 5 is missing and the run stops at length 4.

Pseudocode

put every number into a set
longest = 0
for each num in the set:
    if num - 1 is NOT in the set:        # num begins a run
        length = 1
        nxt = num + 1
        while nxt is in the set:          # walk the run forward
            length += 1
            nxt += 1
        longest = max(longest, length)
return longest

The Python solution

def longest_consecutive(nums):
    num_set = set(nums)
    longest = 0
    for num in num_set:
        if num - 1 not in num_set:
            length = 1
            nxt = num + 1
            while nxt in num_set:
                length += 1
                nxt += 1
            longest = max(longest, length)
    return longest

• num_set = set(nums) gives O(1) membership tests and drops duplicates for free.
• Line 5 — num - 1 not in num_set — is the heart of the trick: it only lets us start a run at its leftmost number.
• The while loop walks forward from a confirmed start, extending length while the next integer exists.
• longest = max(...) keeps the best run seen so far.

Complexity

It looks like the nested while could make it O(n²), but the start guard means each number is touched at most twice — once in the outer loop, once while walking a run — so it is O(n).

When this pattern shows up

Practice