Skip to main content

68. Longest Consecutive Sequence

mediumAsked at Datadog

Find the longest sequence of consecutive integers in an unsorted array in O(n). Datadog asks this for the start-only expansion trick — same pattern as compacting consecutive timestamps in a sparse metric block.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite — direct analog to timestamp compaction.
  • Blind (2025-11)— Recurring Datadog problem.

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: [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; iterate counting consecutive runs.

Time
O(n log n)
Space
O(1)
function longestConsecutive(nums) {
  if (nums.length === 0) return 0;
  nums = nums.slice().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++;
    else curr = 1;
    best = Math.max(best, curr);
  }
  return best;
}

Tradeoff: Works but violates the O(n) constraint.

2. Hashset + start-only expansion (optimal)

Put all values in a Set. For each value, expand ONLY if value-1 is NOT in the set (i.e., this is the start of a run).

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

Tradeoff: O(n) total — each value is visited at most twice (once as a non-start skip, once as part of a run). Datadog-canonical.

Datadog-specific tips

Datadog grades on the start-only expansion. Without it, the inner while loop turns the algorithm O(n^2). The key insight — only expand from a value whose predecessor isn't present — is what they're checking.

Common mistakes

  • Expanding from every value — each run is rediscovered O(length) times, giving O(n^2).
  • Not handling duplicates — the Set deduplicates naturally, but counting them would double-count.
  • Returning best = 1 for non-empty input — should start at 0 and update inside the loop, or initialize to 1 only if the input is non-empty.

Follow-up questions

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

  • Datadog-style: compact consecutive timestamps in a sparse metric block.
  • Union-Find variant — group consecutive values into the same set.
  • Binary Indexed Tree on the value space — for streaming variants.

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 start-only expansion O(n)?

Each value is visited at most twice: once when iterating the outer Set (O(n) total), and once when it's part of an inner expansion (which only happens to start-values). So total work is bounded by 2n.

What about negative numbers?

Hashset works regardless of sign. The 'x - 1' check is in integer space, fine for negatives.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →