Skip to main content

128. Longest Consecutive Sequence

mediumAsked at Netflix

Given an unsorted array, find the longest run of consecutive integers (any order in the array). Netflix asks this because the obvious sort-then-scan is O(n log n) — and the question is whether you reach for the hash-set 'only start a chain at a true start' trick for O(n).

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Netflix loops.

  • Glassdoor (2026-Q1)— Netflix L4 onsite reports cite this as the array problem that probes hash-set fluency.
  • Blind (2025-12)— Netflix SWE writeups consistently mention the 'only start chains at num-1 not in set' trick as the signal.

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.

Constraints

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

Examples

Example 1

Input
nums = [100,4,200,1,3,2]
Output
4

Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Example 2

Input
nums = [0,3,7,2,5,8,4,6,0,1]
Output
9

Approaches

1. Sort then scan

Sort, then walk once tracking consecutive runs.

Time
O(n log n)
Space
O(1) or O(n) depending on sort
function longestConsecutiveSort(nums) {
  if (nums.length === 0) return 0;
  nums.sort((a, b) => a - b);
  let best = 1, cur = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] === nums[i - 1]) continue;
    if (nums[i] === nums[i - 1] + 1) cur++;
    else cur = 1;
    best = Math.max(best, cur);
  }
  return best;
}

Tradeoff: Correct but the problem explicitly demands O(n) — sort-then-scan fails the requirement signal even though it produces the right answer.

2. Hash set with chain-start check (optimal)

Insert all values into a Set. For each num, only START counting a chain if num - 1 is NOT in the set — this guarantees you walk each chain exactly once.

Time
O(n)
Space
O(n)
function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const num of set) {
    if (set.has(num - 1)) continue;
    let cur = num, len = 1;
    while (set.has(cur + 1)) { cur++; len++; }
    best = Math.max(best, len);
  }
  return best;
}

Tradeoff: O(n) amortized. The trick: 'only start a chain at its smallest element' means each chain is walked once total, so the total work across all starts is O(n).

Netflix-specific tips

Netflix interviewers specifically grade whether you spot the 'only start a chain at a true start' optimization. Without it, you'd walk each chain from every element in it — O(n^2). Articulate it: 'I'll iterate over the set, but only start counting if num - 1 isn't in the set, which guarantees we hit each chain once.' That sentence is the entire optimization.

Common mistakes

  • Walking chains from every element (no chain-start check) — accidentally O(n^2).
  • Iterating over `nums` instead of the Set — duplicates cause double work.
  • Forgetting the empty-input case (return 0) — the while loop never sets best.

Follow-up questions

An interviewer at Netflix may pivot to one of these next:

  • What if the array were sorted? (Linear scan is trivial — O(n).)
  • What if values could be added or removed online? (Union-find by integer becomes attractive.)
  • Could you return the actual sequence, not just its length?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the chain-start check necessary for O(n)?

Without it, you'd start walking a chain from every element in it. For a chain of length k, that's k * k = k^2 work. Across all chains, that's O(n^2) in the worst case (one big chain). The chain-start check guarantees you walk each chain exactly once total.

Could you use a Union-Find instead?

Yes — union each num with num + 1 if num + 1 exists in the set. Track component sizes; return the max. Same O(n alpha(n)) complexity but heavier — the hash-set approach is preferred for its simplicity.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Longest Consecutive Sequence and other Netflix interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →