Skip to main content

128. Longest Consecutive Sequence

mediumAsked at Google

Given an unsorted array, find the length of the longest consecutive elements sequence. The catch: Google requires O(n) — sorting (O(n log n)) is the wrong answer and you must reach for the hash-set 'start a chain only from the smallest element' trick.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4 onsite reports cite this with the explicit O(n) requirement.
  • Blind (2025-09)— Recurring Google interview question with sorting explicitly disallowed.

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].

Example 2

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

Approaches

1. Sort + scan

Sort the array, then sweep to find the longest run of consecutive values.

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

Tradeoff: Violates the O(n) requirement. Use this only to anchor the comparison and show you noticed sorting won't work.

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

Put all elements in a set. For each element that is the START of a sequence (set doesn't contain n-1), walk forward and count.

Time
O(n)
Space
O(n)
function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const n of set) {
    if (set.has(n - 1)) continue; // only start chains from the smallest element
    let curr = n;
    let len = 1;
    while (set.has(curr + 1)) {
      curr++;
      len++;
    }
    best = Math.max(best, len);
  }
  return best;
}

Tradeoff: Linear time because each value is touched at most twice (once as a chain start, once during walk). The key trick: only walk forward from chain starts, so total work across all walks is bounded by n.

Google-specific tips

Google interviewers specifically value the analysis that proves this is O(n) and not O(n^2). State out loud: 'Each value is touched at most twice — once when we check if it's a chain start, and at most once during a forward walk because we only walk forward from the smallest element of each chain.' Without that articulation, the interviewer can't tell if you got lucky.

Common mistakes

  • Walking forward from EVERY element instead of just chain starts — that's O(n^2).
  • Reaching for sorting and forgetting the O(n) requirement.
  • Forgetting to deduplicate (the set does this automatically; an array doesn't).

Follow-up questions

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

  • What if you needed the actual sequence, not just its length?
  • Could you do it with O(1) extra space? (Yes, with union-find or sort — but those aren't O(n).)
  • What if the input is a stream?

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 this O(n) and not O(n^2)?

Each element is visited at most twice — once during the chain-start check (O(1)) and at most once during a forward walk. The chain-start check is the key: it ensures we walk each sequence exactly once.

What's the most-common bug in interviews?

Forgetting the chain-start check (set.has(n - 1) continue). Without it, the worst case becomes O(n^2) when the input is a single long sequence.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →