Longest Consecutive Sequence: The O(n) Trick That Looks Impossible

Given a bag of unsorted integers, find the length of the longest run of consecutive values — numbers that would sit shoulder to shoulder if you laid them on a number line. The catch: you have to do it in O(n) time, which rules out the sorting solution that first comes to mind.

That constraint is the whole puzzle. Sorting makes consecutive runs trivial to spot, but sorting is O(n log n). The linear answer needs a different lever: a hash set, plus one small rule about where a sequence is allowed to start.

Get that rule right and each number is touched at most twice across the entire run. Get it wrong and you write an O(n²) disaster that looks correct on small inputs.

The problem#

You're given an unsorted array of integers nums. Return the length of the longest sequence of consecutive integers. The numbers don't need to be adjacent in the array — only consecutive in value. Duplicates don't extend a run.

Notice that 1, 2, 3, 4 are scattered across the array (indices 3, 5, 4, 1) and interrupted by 100 and 200. Order of appearance is irrelevant; only the values and whether their neighbors exist matter. The answer is the length of the longest such chain — here, four.

The brute force baseline#

The naive idea: for every number, walk upward as far as the chain continues, checking membership with a linear scan each time.

This is correct but brutally slow. nums.includes(...) is an O(n) scan, it runs inside a while loop, and the whole thing is wrapped in a for loop over every element. That's O(n³) in the worst case. Even if you swap includes for a hash set, starting a walk from every number — including numbers in the middle of a chain — re-walks the same run over and over, which is where the real waste hides.

The key insight: only start from a sequence start#

The reframe is one question: who is allowed to begin a walk?

A number num is the start of a consecutive sequence only if num - 1 is not present. If num - 1 exists, then num sits in the middle (or end) of some longer chain, and that chain will get walked when we reach its real start. So we skip it entirely.

This is the pattern named Hash Set + Sequence Start. The set gives O(1) membership; the "no predecessor" gate guarantees each chain is walked exactly once, from its bottom. That single rule is what collapses the work from quadratic to linear.

The optimal solution#

Put every number in a Set (which also deduplicates for free), then only launch the inner walk from values that have no predecessor.

Two things carry the whole solution. First, iterating over numSet instead of nums means duplicates are visited once — [1, 2, 2, 3] behaves exactly like [1, 2, 3]. Second, the if (!numSet.has(num - 1)) gate is the O(n) guarantee: the inner while only ever runs from the bottom of a chain, so across all starts the walk steps sum to at most the number of unique values.

Walkthrough#

Trace nums = [100, 4, 200, 1, 3, 2]. The set is {100, 4, 200, 1, 3, 2}, iterated in insertion order. For each value we check its predecessor, and only walk when it's a start.

The payoff row is num = 1. Because 0 is absent, 1 is a genuine start, so the walk fires: it finds 2, 3, 4 in the set and stops at the missing 5, yielding len = 4. Every other member of that chain (2, 3, 4) was correctly skipped because each had a predecessor. Total walk steps across the whole run: five — never re-walking a chain is exactly what keeps this linear.

Complexity#

The linear claim surprises people because there's a while inside a for. But the start gate means the inner loop only advances along a chain from its bottom, and no value belongs to two chains. So the combined walk length is bounded by n, not n². Space is O(n) for the set.

Common mistakes#

• Walking from every number, not just starts. Drop the if (!numSet.has(num - 1)) gate and you re-walk 1→2→3→4, then 2→3→4, then 3→4... That's O(n²), the exact trap the gate exists to prevent.
• Iterating nums instead of numSet. Duplicates then trigger redundant start checks and can inflate your step count. Iterating the set keeps every unique value to a single visit.
• Forgetting the empty-array case. With no elements, best stays 0, which is the correct answer — but only if you initialized best = 0 rather than 1.
• Reaching for sorting reflexively. Sorting works and is easy to reason about, but it's O(n log n). If the interviewer asks for O(n), the hash-set start trick is the intended answer.

Where this pattern shows up next#

The "process each element once by picking the right anchor" idea recurs across array problems:

• Remove Duplicates from Sorted Array — a single pass that keeps one copy of each value, close kin to the dedup a Set gives you here.
• Remove Element — in-place filtering in one linear scan with a write pointer.
• Reverse String — the two-pointer counterpart to single-pass array work.
• Best Time to Buy and Sell Stock — one pass tracking a running best, the same best = Math.max(...) shape.

You can also step through Longest Consecutive Sequence interactively to watch the set fill, the start gate fire, and each chain light up on the number line.

FAQ#

Why is Longest Consecutive Sequence O(n) and not O(n²)?#

Because the inner while loop only runs from the start of a sequence — a value whose predecessor is absent. Every number belongs to exactly one chain, and each chain is walked exactly once from its bottom. So the total number of walk steps across all starts is bounded by the number of unique values, not multiplied by it. The nested loop looks quadratic but the sequence-start gate makes the combined inner work linear.

Can't I just sort the array and count consecutive runs?#

Yes, and it's a perfectly valid solution: sort, then do a single pass counting runs of nums[i] === nums[i-1] + 1. It's simpler to write. The only downside is O(n log n) time from the sort. When the problem specifically demands O(n), the hash-set approach is the one that meets the bar, which is why interviewers usually push you toward it.

How does the solution handle duplicate numbers?#

Building new Set(nums) removes duplicates before any counting happens, so [1, 2, 2, 3, 3, 4] collapses to {1, 2, 3, 4} and returns 4. Because we iterate over the set rather than the raw array, each unique value is visited once and duplicates can neither extend a run nor cause redundant walks.

What should the function return for an empty array?#

Zero. With no elements, the set is empty, the for loop never runs, and best keeps its initial value of 0. This is the correct answer — an empty array has no consecutive sequence. Just make sure you initialize best = 0 and not 1, since a 1 default would wrongly report a length for empty input.