Skip to main content

128. Longest Consecutive Sequence

mediumAsked at Shopify

Shopify uses this to grade whether you spot the 'only start a chain at a candidate that's NOT preceded by val-1' trick. Without it, the obvious set-walk is O(n^2); with it, it's O(n).

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

Source citations

Public interview reports confirming this problem appears in Shopify loops.

  • Glassdoor (2026-Q1)— Shopify Backend Developer + Senior Engineering onsites cite this as a medium hash-set round.
  • Reddit r/cscareerquestions (2025-10)— Shopify interview reports include this with the O(n) constraint explicit.

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 sequence is [1,2,3,4].

Example 2

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

Approaches

1. Sort then sweep

Sort the array, walk it, counting the current run; reset on a gap, skip duplicates.

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

Tradeoff: Correct and easy, but violates the explicit O(n) constraint. Use only as the warmup explanation.

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

Throw everything into a Set. For each num, only start a chain if num-1 is NOT in the set (meaning num is the smallest of its chain). Walk num, num+1, num+2, ... while the set contains them.

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 current = num;
    let run = 1;
    while (set.has(current + 1)) {
      current++;
      run++;
    }
    best = Math.max(best, run);
  }
  return best;
}

Tradeoff: Each chain is walked exactly once because we only enter the inner while from the chain start. Total inner-loop work across the whole run is O(n). The 'continue' guard is the entire trick — without it, this would be O(n^2).

3. Union-Find

Add each num to a DSU; on insert, union with num-1 and num+1 if they exist. Track the largest set size.

Time
O(n a(n))
Space
O(n)
function longestConsecutiveUF(nums) {
  const parent = new Map();
  const size = new Map();
  function find(x) {
    while (parent.get(x) !== x) {
      parent.set(x, parent.get(parent.get(x)));
      x = parent.get(x);
    }
    return x;
  }
  function union(a, b) {
    const ra = find(a), rb = find(b);
    if (ra === rb) return;
    if (size.get(ra) < size.get(rb)) {
      parent.set(ra, rb);
      size.set(rb, size.get(rb) + size.get(ra));
    } else {
      parent.set(rb, ra);
      size.set(ra, size.get(ra) + size.get(rb));
    }
  }
  for (const n of nums) {
    if (parent.has(n)) continue;
    parent.set(n, n);
    size.set(n, 1);
    if (parent.has(n - 1)) union(n, n - 1);
    if (parent.has(n + 1)) union(n, n + 1);
  }
  let best = 0;
  for (const s of size.values()) best = Math.max(best, s);
  return best;
}

Tradeoff: Asymptotically O(n a(n)) ~ O(n), but with a big constant and more code. Bring it up only if the interviewer pushes on alternatives — most Shopify graders prefer the set-with-filter version because it's tighter.

Shopify-specific tips

Shopify will mark you down if you write the set version WITHOUT the chain-start filter — that's the O(n^2) trap. Always say 'we only kick off a walk from the chain's smallest element' BEFORE coding. The interviewer is grading whether you spot the amortization argument, not just the data-structure choice.

Common mistakes

  • Forgetting the `if (set.has(num - 1)) continue;` guard — turns O(n) into O(n^2).
  • Using `nums` instead of `set` in the outer loop — iterates duplicates, blowing up the runtime.
  • Off-by-one — best starts at 0 (handles empty input); run starts at 1 because we count num itself.
  • Mutating the set during iteration (common with .delete) — breaks iterator semantics in some engines.

Follow-up questions

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

  • Return the actual sequence, not just its length.
  • Stream version — numbers arrive one at a time.
  • Find the K longest disjoint consecutive sequences.
  • What if the input contains negative numbers and very large numbers (already handled by Set, but discuss).
  • What if duplicates count (e.g. [1,1,2,3] -> length 4 not 3)?

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 filter the key to O(n)?

Without it, you'd walk every chain starting from every element of that chain, doing O(L) work per element where L is chain length — total O(n*L) = O(n^2). With the filter, each chain is walked exactly once (from its smallest element). Each element is visited at most twice: once in the outer for-loop and once in an inner while.

Could you do this with a sorted multiset in O(n log n)?

Yes, but it violates the constraint. The constraint exists precisely to force the hash-set + amortization trick. Sort-then-sweep is the second-best answer to verbalize.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →