Longest consecutive sequence - hash-set sequence heads

You’ve used a hash set for membership (Day 4). You’ve sorted to group related items (Day 12). The trap on this problem is thinking you must sort. Sorting works. The interview upgrade is realizing consecutive runs have heads - and a set can find heads in O(1).

The problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

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

Input:  [100, 4, 200, 1, 3, 2]
Output: 4
// The longest consecutive sequence is [1, 2, 3, 4]

Order in the array does not matter. Duplicates do not extend the sequence. Empty array → 0.

Approach 1: Brute - for each number, hunt the next

For every value n, keep asking “is n+1 in the array?” with includes (linear scan). Stretch the run as far as it goes. Track the max length.

// Brute - O(n²) typical (worse with long runs)
function longestConsecutiveBrute(nums) {
  if (nums.length === 0) return 0;
  let best = 1;
  for (const n of nums) {
    let length = 1;
    let cur = n;
    while (nums.includes(cur + 1)) {  // O(n) each probe
      cur += 1;
      length += 1;
    }
    if (length > best) best = length;
  }
  return best;
}

Correct, and catastrophically slow once runs get long: every step of a run re-scans the array.

Approach 2: Sort, then scan - O(n log n)

Sort a copy. Walk adjacent values. Skip duplicates. When sorted[i] === sorted[i-1] + 1, grow the current streak; otherwise reset.

// Sort - O(n log n) time, O(n) space for the copy
function longestConsecutiveSort(nums) {
  if (nums.length === 0) return 0;
  const sorted = [...nums].sort((a, b) => a - b);
  let best = 1, cur = 1;
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1]) continue;
    if (sorted[i] === sorted[i - 1] + 1) {
      cur += 1;
      if (cur > best) best = cur;
    } else {
      cur = 1;
    }
  }
  return best;
}

Clean and interview-safe when O(n log n) is allowed. The problem statement asks for O(n) - so we need one more move.

Approach 3: Hash set + sequence heads - amortized O(n)

Put every number in a Set (O(n)). For each number n, ask: is n the start of a sequence? A start means n - 1 is not in the set. Only then count forward with n+1, n+2, … while those values exist.

// Hash set - amortized O(n) time, O(n) space
function longestConsecutive(nums) {
  if (nums.length === 0) return 0;
  const set = new Set(nums);
  let best = 1;
  for (const n of set) {
    if (set.has(n - 1)) continue; // not a sequence head - skip
    let length = 1;
    let cur = n;
    while (set.has(cur + 1)) {
      cur += 1;
      length += 1;
    }
    if (length > best) best = length;
  }
  return best;
}

Worked example: [100, 4, 200, 1, 3, 2]

set = {100, 4, 200, 1, 3, 2}

n=100: 99 missing → head. count 100 only → length 1
n=4:   3 present  → skip (not a head)
n=200: 199 missing → head. length 1
n=1:   0 missing  → head. 1→2→3→4 → length 4  ✓
n=3:   2 present  → skip
n=2:   1 present  → skip

best = 4

Why O(n)? Each number is the start of at most one forward walk. Across the whole algorithm, every value is visited a constant number of times (membership checks + at most one expansion step as part of some run). Total work is linear in the size of the set.

Benchmark - correctness first, then speed

Recorded from a real Node.js benchmark, 30-run medians (brute at n=5K: 10 runs). The script and standalone write-up are not included in this repository.

Mixed runs (several short consecutive blocks + noise)

n	Brute	Sort	Hash-set
1,000	2.020 ms	0.197 ms	0.070 ms
5,000	51.484 ms	0.829 ms	0.413 ms
50,000	-	10.858 ms	4.886 ms

Headline: at n=5,000 mixed, hash-set is 124.7× faster than brute (51.484 / 0.413). At n=50,000 mixed, hash-set is 2.2× faster than sort (10.858 / 4.886).

Dense (one long consecutive run of ~n/2)

n	Sort	Hash-set	Sort / set
10,000	1.737 ms	0.839 ms	2.1×
50,000	11.742 ms	4.970 ms	2.4×
100,000	27.000 ms	27.688 ms	~1.0× (tie)

Honest note (same family as Day 18 bucket sort and Day 25 escape constants): at dense n=100K, V8’s sort and Set overhead converge - sort can match or slightly beat the O(n) set. The O(n) pattern still wins cleanly through mid sizes and on mixed data. Do not claim “always faster at every n.”

What breaks?

• Expanding from every element → O(L²) on a run of length L. The head check is mandatory for the complexity claim.
• Using a list instead of a set for membership → each has becomes O(n); you are back to brute.
• Forgetting duplicates → sort approach double-counts if you don’t skip equal neighbors; set approach is naturally de-duplicated.
• Assuming sort is “cheating” - sort is valid if the interviewer allows O(n log n). The O(n) constraint is what forces the set insight.

Connection to previous days

• Day 4 (Contains Duplicate): same data structure - hash set for O(1) membership. Day 4 asks “seen before?” Day 26 asks “is the previous integer present?”
• Day 11 (Two Sum): complement thinking. Here the “complement” of a head is the missing n-1.
• Day 18 (Top K): Big O vs wall clock. O(n) set vs O(n log n) sort can tie at large dense n - constants matter.
• Day 19 (Product except self): both reward a reframe. Day 19: before × after. Day 26: only expand from heads.
• Day 25 (Encode/Decode): “what breaks on the edge case?” pedagogy continues - wrong expansion rule silently destroys complexity, not just correctness.

Quiz