Q31: Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence in $O(n)$ time.

Hash Set Sequence Detection

function longestConsecutive(nums) {
  const numSet = new Set(nums);
  let longest = 0;
  
  for (let num of numSet) {
    // Check if num is the start of a sequence
    if (!numSet.has(num - 1)) {
      let currentNum = num;
      let currentStreak = 1;
      
      while (numSet.has(currentNum + 1)) {
        currentNum++;
        currentStreak++;
      }
      longest = Math.max(longest, currentStreak);
    }
  }
  return longest;
}

console.log(longestConsecutive([100, 4, 200, 1, 3, 2])); // 4 ([1, 2, 3, 4])

💡 Converts array to Set. Loops through set, identifying sequence starters (num - 1 missing). From starters, increments currentNum upward, measuring sequence length in $O(n)$ overall operations.

Key Takeaways

Store numbers in a Hash Set to perform $O(1)$ presence lookups.
Only attempt to build sequences from the start of a sequence (!set.has(num - 1)).

Knowledge Check

Why does the inner while loop not degrade the algorithm time complexity to O(N²)?

Q31: Longest Consecutive Sequence

STAY UPDATED WITH BYTES!