4.4.9 — Longest Consecutive Sequence

LeetCode 128 · Medium · ★ Blind 75

The problem

Find the length of the longest run of consecutive integers present in an unsorted array. They do not have to be next to each other in the array, only present.

[100, 4, 200, 1, 3, 2]     →  4    (1, 2, 3, 4)
[0,3,7,2,5,8,4,6,0,1]      →  9    (0 through 8)
[]                         →  0

Up to 100,000 numbers, each between -10^9 and 10^9. The problem requires O(n).

That requirement is the difficulty. Sorting answers it in six lines and is O(n \log n), so it is ruled out.

The sorting answer first

nums = sorted(set(nums))
best = length = 1
for i in range(1, len(nums)):
    if nums[i] == nums[i - 1] + 1:
        length += 1
        best = max(best, length)
    else:
        length = 1

Deduplicating with set(nums) before sorting removes the need for a third branch handling equal neighbours.

Say this out loud before attacking the real solution. Then say what moves you forward: sorting gives me the full order, but I only need to know which numbers exist and whether the next one up exists. That is membership, and membership does not need order.

The pattern

Put everything in a set, so n + 1 in s is a constant-time question. Now you could walk any run forward from its start.

The problem is that walking from every number re-walks the same run once per member. [1,2,3,4] gets walked from 1, then 2, then 3, then 4. That is O(n^2) and you are back where you started.

The fix is one line, and it is the whole algorithm:

Only start walking from a number that begins a run. A number n begins a run exactly when n - 1 is not in the set.

If n - 1 exists, then n sits in the middle of a run that will be walked from its true start anyway. Skip it.

The solution

Python

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

        for n in s:
            if n - 1 in s:          # not a run start — skip
                continue
            length = 1
            while n + length in s:
                length += 1
            best = max(best, length)

        return best

TypeScript

function longestConsecutive(nums: number[]): number {
  const s = new Set(nums);
  let best = 0;

  for (const n of s) {
    if (s.has(n - 1)) continue;
    let length = 1;
    while (s.has(n + length)) length++;
    best = Math.max(best, length);
  }

  return best;
}

set(nums) does two jobs: it gives O(1) membership, and it removes duplicates so [1,1,2] correctly reports 2 rather than 3.

Iterate the set, not the array. Iterating the array visits a duplicated value once per copy and repeats the run-start check each time. It stays correct but it wastes work and it breaks the complexity argument below.

best starts at 0, so an empty input returns 0 with no special case.

Trace

[100, 4, 200, 1, 3, 2], so s = {1, 2, 3, 4, 100, 200}.

n	n-1 present?	what happens	inner steps
1	no	walk 2, 3, 4 → length 4	4
2	yes	skip	0
3	yes	skip	0
4	yes	skip	0
100	no	length 1	1
200	no	length 1	1

Six inner steps for six distinct numbers. That is not a coincidence.

Why this is O(n), not O(n^2)

This is why the problem is asked. There is a while inside a for, and nested loops normally multiply. Here they do not, and you need to be able to say why on demand.

The wrong reading assumes the inner loop can run long on every outer iteration. It cannot. Count the total work across the whole program instead of per iteration:

1. The inner loop only runs when n starts a run, because of the skip.
2. When it runs, it walks that run once, start to end.
3. Every number belongs to exactly one run — two runs sharing a number would be the same run.
4. So each number is stepped over by the inner loop at most once in the entire program.

Total inner work is therefore bounded by the number of distinct values, at most n. The outer loop separately does O(1) per value. O(n) overall, O(n) space.

This is amortized analysis: charge each unit of work to a distinct element, then show no element can be charged twice. You meet the identical argument three more times in Part 4 — the monotonic stack (4.8), where each index is pushed once and popped once; the sliding window (4.6), where the left pointer only moves right; and Manacher (4.31), where the centre never moves back. Seeing them as one argument is worth more than remembering three.

The mistake that quietly costs the linear time

Drop the n - 1 guard and the code still returns the right answer — it just becomes quadratic. There is no error and no failing test, only a timeout on the largest input. That is the failure mode to watch for.

The union-find alternative

Treat each number as a node and union n with n + 1 when both exist. The answer is the largest component size. It works and it is effectively linear, but it is more code, more memory, and slower here.

It earns its place when numbers arrive over time and you must answer queries in between — the set version needs a full pass before it can answer anything. Chapter 4.19.2 builds union-find.

Edge cases

Empty array returns 0. All duplicates gives 1. Values spanning zero are fine, since the set does arithmetic on keys without caring about sign.

The \pm 10^9 range matters in one way: it rules out marking values in an array indexed by value. Two billion slots for a hundred thousand values is far too sparse, so hashing is the only reasonable structure.

Where this goes next

• Longest Consecutive Sequence in a Binary Tree — same words, different problem: the run must follow parent-to-child links, so it is a tree DFS. Worth knowing so you do not misfile it.
• Longest Harmonious Subsequence — the longest span where max and min differ by exactly 1. A counting map and one lookup of n + 1, no walking.

The move has two levels. Narrowly: use a set for membership and find each group from an agreed starting point. Generally: do the work only from one canonical member of each group. That same guard shows up as "only flood-fill from an unvisited cell" in 4.20.

What the interviewer will push on

"There is a loop inside a loop. Why is it not O(n^2)?" This is asked on this problem more reliably than any other in the group, because the code looks quadratic. Give the four-step argument.

"Why check n - 1 and not n + 1?" You need one agreed starting point per run, and the smallest element is the natural one. Checking n + 1 finds run ends and works too if you then walk downwards.

"What if you had to return the sequence itself?" Track the starting value alongside the best length. One extra variable.

"What if the numbers arrive as a stream?" The set version needs a full pass, so it does not adapt. Union-find does — union each arrival with its neighbours and keep a running maximum.

One thing to volunteer: give the linearity proof before they ask for it. Volunteering the proof of your own complexity claim is one of the strongest signals available.

Next: 4.5 drops the hash map and kills the nested loop a different way — two indices moving through one array, under a rule that proves neither ever needs to go back.