Skip to main content

128. Longest Consecutive Sequence

hardAsked at LinkedIn

Find the length of the longest run of consecutive integers in an unsorted array in O(n) time — LinkedIn uses this problem to check whether you can design set-based O(n) algorithms, the same reasoning they apply to detecting unbroken skill-progression sequences in member credential timelines.

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

Problem

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. The algorithm must run 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] with length 4.

Example 2

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

Approaches

1. Sort — O(n log n) violates the constraint

Sort the array, then scan for consecutive runs. Clear and easy but O(n log n) — fails the O(n) requirement. Name it first to set up the hash set approach.

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:

2. Hash set — start-of-sequence detection — O(n) optimal

Load all numbers into a Set. For each number n, check if n-1 is NOT in the set — if so, n is the start of a sequence. Count forward until the sequence breaks. Each number is visited at most twice total (once as start check, once in a streak count), giving O(n) overall.

Time
O(n)
Space
O(n)
function longestConsecutive(nums) {
  const numSet = new Set(nums);
  let best = 0;
  for (const n of numSet) {
    if (!numSet.has(n - 1)) { // n is a sequence start
      let curr = n, streak = 1;
      while (numSet.has(curr + 1)) { curr++; streak++; }
      best = Math.max(best, streak);
    }
  }
  return best;
}

Tradeoff:

LinkedIn-specific tips

LinkedIn grades this on whether you arrive at the O(n) insight without hints. The critical observation to state explicitly: 'I only start counting from sequence beginnings — a number n is a start only if n-1 is absent from the set. This ensures each element participates in exactly one streak, keeping the total work O(n) despite the nested while loop.' Interviewers will probe 'why is the inner while O(n) overall?' — answer with the amortized argument: each element is incremented at most once across all streaks.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →