Skip to main content

128. Longest Consecutive Sequence

mediumAsked at Robinhood

Given an unsorted array of integers, return the length of the longest consecutive elements sequence. Robinhood asks this for the surprise O(n) insight — sort feels right but the hash-set trick beats it cleanly.

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

Source citations

Public interview reports confirming this problem appears in Robinhood loops.

  • Glassdoor (2026-Q1)— Robinhood SWE phone-screen reports list Longest Consecutive Sequence as a recurring problem.
  • Blind (2025-10)— Robinhood new-grad trip reports cite this as a favorite for the O(n) insight.

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 + scan

Sort the array. Walk and count consecutive runs, resetting on gaps and skipping duplicates.

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

Tradeoff: Easy to write and reason about, but doesn't meet the O(n) bar the problem explicitly demands.

2. Hash set with sequence-start optimization (optimal)

Build a set of nums. Only start counting a run from x where x-1 is NOT in the set (so each run is counted once).

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

Tradeoff: True O(n) — each number is visited at most twice (once by the outer loop, once by the inner while). The 'only start from sequence-heads' guard is what keeps the inner while from amortizing badly.

Robinhood-specific tips

Robinhood interviewers want to hear the O(n) argument out loud. The trick is the sequence-head guard: 'I only start counting from x if x-1 is NOT in the set, which means each consecutive run is walked exactly once.' Without that guard you'd accidentally re-walk runs and degrade to O(n^2). Iterate the set, not the array, to dedupe automatically.

Common mistakes

  • Forgetting the sequence-head guard — degrades to O(n^2) on long runs.
  • Iterating the input array instead of the set — recomputes the same run for every duplicate.
  • Returning the run itself instead of its length.

Follow-up questions

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

  • Binary Tree Longest Consecutive Sequence — same shape on a tree.
  • Longest Increasing Subsequence (not consecutive) — different problem; needs DP/patience sort.
  • Streaming variant — return the longest run seen so far as numbers arrive.

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

Because the inner while only runs when starting from a sequence head (n-1 not in set). Each number is the right-of n only for the head of its own run, so the total work across all while loops is O(n).

Can the set lookup itself be O(1)?

JS Set.has is amortized O(1) on hash. Worst-case adversarial inputs could degrade, but for integer keys this is fine.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →