Skip to main content

82. Longest Consecutive Sequence

mediumAsked at Ola

Find the length of the longest consecutive integer sequence in an unsorted array.

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. Algorithm must run in O(n).

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

Example 2

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

Approaches

1. Sort then scan

Sort the array; walk and count maximal consecutive runs.

Time
O(n log n)
Space
O(1)
nums = [...new Set(nums)].sort((a,b)=>a-b);
let best = 0, cur = 0;
for (let i=0;i<nums.length;i++) { cur = (i===0 || nums[i] !== nums[i-1]+1) ? 1 : cur + 1; best = Math.max(best, cur); }
return best;

Tradeoff:

2. Hash set with sequence start

Put all values in a set; for each value with no predecessor, extend forward and track the longest streak.

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

Tradeoff:

Ola-specific tips

Ola interviewers want to see why the sequence-start filter keeps the work linear; tie it to spotting the longest contiguous block of active driver-shift hours.

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 Ola interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →