Longest Consecutive Sequence

MediumArrays & HashingArrayHash TableUnion Find

Problem

You are given an unsorted array of integers. Find the length of the longest run of consecutive integers that appear somewhere in the array; the values need not be adjacent in the array itself, only present as a set.

Example. For [100, 4, 200, 1, 3, 2], the values 1, 2, 3, 4 are all present, forming a run of length 4, which is the answer.

Key idea

Sorting the array first makes consecutive runs sit next to each other, so a single scan afterward finds the longest run in O(n log n) total. That works, but it is not the fastest option.

To do better, drop every value into a hash set so membership can be checked in O(1). The key trick is to only start counting a run from a number that is genuinely the start of one, meaning number - 1 is not in the set. For each such starting number, walk upward, checking whether number + 1, number + 2, and so on are present, and track how far the run extends. Numbers in the middle of a run are skipped as starting points rather than re-explored. Because every number is walked at most once, as part of the single run it belongs to, the total work across every start adds up to O(n) despite the nested-loop appearance.

Solution

function longestConsecutive(nums: number[]): number {
  const values = new Set(nums);
  let longest = 0;

  for (const num of values) {
    if (values.has(num - 1)) {
      continue; // not the start of a run, it will be counted from its actual start
    }

    let length = 1;
    let current = num;
    while (values.has(current + 1)) { // extend the run while it stays consecutive
      current++;
      length++;
    }

    longest = Math.max(longest, length);
  }

  return longest;
}

Complexity

  • Time: O(n). The set build is O(n), and every number is visited a bounded number of times across all run walks combined.
  • Space: O(n). The hash set holds every distinct value.

Watch out for

  • Skipping the "is this a start" check turns the algorithm back into O(n²), since interior numbers would redundantly re-walk runs they already belong to.
  • Duplicate values do not extend a run and should not be double-counted; a set naturally collapses them.
  • An empty array should return 0 rather than assuming at least one element exists.

Pattern

This is hash-set membership combined with "only extend from a boundary." A union-find structure can solve the same grouping problem, but walking from detected starts is the simpler idiomatic fit here, and the same space-for-speed trade recurs anywhere a full rescan needs to be avoided.

Related questions