Longest Consecutive Sequence

The problem

Unsorted integers. Return length of the longest consecutive elements sequence. Algorithm should run in O(n).

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

Brute: sort unique

function longestConsecutiveSort(nums: number[]): number {
  if (!nums.length) return 0;
  const a = [...new Set(nums)].sort((x, y) => x - y);
  let best = 1;
  let cur = 1;
  for (let i = 1; i < a.length; i++) {
    if (a[i] === a[i - 1] + 1) {
      cur++;
      best = Math.max(best, cur);
    } else cur = 1;
  }
  return best;
}

Time	O(n log n)
Space	O(n)

Good baseline; problem asks for O(n).

Optimal: Set + start of streak only

1. Put all values in a Set.
2. For each x, if x-1 is not in the set, x starts a sequence.
3. Count upward while x+len exists.
4. Track max length.

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

  for (const x of set) {
    if (set.has(x - 1)) continue; // not a start
    let len = 1;
    while (set.has(x + len)) len++;
    best = Math.max(best, len);
  }
  return best;
}

Time	O(n) average — each number visited constant times in while
Space	O(n)

Why O(n)?

Inner while only runs for streak starts; across all starts, each element is scanned once as a streak member.

Edge cases

• Empty → 0
• All duplicates → 1
• Negatives
• Single element

Common mistakes

• Starting a count from every number → O(n²)
• Using object keys and forgetting negatives
• Sorting and claiming O(n)

Interview delivery

1. O(n) required.
2. Set membership.
3. Only expand from sequence starts.
4. Amortized linear proof one-liner.
5. Empty case.

Mental model

Put numbers in a hash set so x+1 probes are O(1). Only start counting from numbers that have no predecessor — each streak is scanned once, giving amortized linear time despite the nested loop shape.

Proof sketch

Every number is the start of at most one streak check. Inside the while, each number is visited as a member at most once across the whole algorithm. Total probes O(n).

Out-loud answer

“O(n) longest consecutive run. Set of values; for each x missing x-1, count upward. Track max length. Sorting is simpler but O(n log n). Empty → 0.”

Complexity table

Approach	Time	Space	Meets O(n) ask?
Sort unique	O(n log n)	O(n)	no
Set + start only	O(n) avg	O(n)	yes
Union-find	O(n α(n))	O(n)	yes, heavier

Interview delivery

1. Need O(n).
2. Hash set.
3. Expand only from streak heads.
4. Amortized linear.
5. Empty and duplicates.

Related

• Contains Duplicate
• Two Sum
• Group Anagrams
• Longest Increasing Subsequence
• JavaScript Interview Guide

Further reading

• LeetCode 128 — Longest Consecutive Sequence
• MDN: Set