Longest Consecutive Sequence

Difficulty: Medium

You're given an unsorted list of integers. Find the length of the longest run of consecutive integers that all appear somewhere in the list - the numbers don't need to sit next to each other in the list itself, only be consecutive in value (like 3, 4, 5, 6).

Your solution needs to run in O(n) time, so sorting the list (which takes longer than that) is a reasonable first attempt, but not the intended final answer.

Examples

Input: nums = [100, 4, 200, 1, 3, 2]
Output: 4

The numbers 1, 2, 3, 4 are all present and form a run of consecutive values - the longest one available.

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

0 through 8 are all present (0 shows up twice, which doesn't extend the run), giving a run of length 9.

Input: nums = []
Output: 0

Constraints

0 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9

Approach

A reasonable first idea is to sort the list - once sorted, consecutive values sit right next to each other, so a single pass counting streaks gives you the answer. It's correct, but sorting itself already costs more than the O(n) the problem is really asking for.

The key insight for a faster solution: put every number into a hash set for instant lookups, then only start counting a sequence from numbers that are the start of one - meaning "number minus 1" is not in the set. Every other number gets picked up later as part of some run starting from its true beginning, so across the whole algorithm, each number only ever gets counted once, even though there's a loop nested inside the main loop.

Solutions

Brute Force - Sort and Scan

Remove duplicates and sort what's left. Then walk through once, tracking how long the current streak of consecutive values is, and remembering the longest streak seen.

function longestConsecutive(nums) {
  if (nums.length === 0) return 0;

  const sorted = [...new Set(nums)].sort((a, b) => a - b);

  let longest = 1;
  let current = 1;

  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1] + 1) {
      current++;
    } else {
      current = 1;
    }
    longest = Math.max(longest, current);
  }

  return longest;
}

Time: O(n log n) · Space: O(n)

Optimal - Hash Set, Start From Sequence Beginnings

Put every number into a hash set. Then, for each number that's the start of a sequence (meaning one less than it is not in the set), count forward - checking if the next value, and the one after that, and so on, are in the set - to find that sequence's length.

function longestConsecutive(nums) {
  const numSet = new Set(nums);
  let longest = 0;

  for (const num of numSet) {
    // Only start counting from the beginning of a sequence
    if (!numSet.has(num - 1)) {
      let length = 1;
      while (numSet.has(num + length)) {
        length++;
      }
      longest = Math.max(longest, length);
    }
  }

  return longest;
}

Time: O(n) · Space: O(n)