Longest Consecutive Sequence

Problem Statement

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in $O(n)$ time.

Example:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Approach: Hash Set

The obvious approach is to sort the array and then count the longest sequence, but sorting takes $O(n \log n)$ time. The problem strictly requires an $O(n)$ solution.

To achieve $O(n)$ time, we can convert the array into a Hash Set. This gives us $O(1)$ lookups for any number. The logic then boils down to identifying the start of a sequence and counting upwards.

A number is the start of a sequence if the number directly preceding it (num - 1) does not exist in the set. If we only count upwards from these “start” numbers, we guarantee that we only traverse each sequence exactly once!

1. Create a Hash Set from the nums array to allow $O(1)$ lookups.
2. Initialize a variable longest = 0 to track the maximum sequence length.
3. Iterate through the elements in the Set.
4. For each num, check if it is the start of a sequence by checking if num - 1 exists in the set.
   • If num - 1 does exist, it is not the start of a sequence. Skip it.
   • If num - 1 does not exist, it is the start of a sequence!
5. When you find a start number, initialize a counter currentLength = 1.
6. Use a while loop to check if num + currentLength exists in the set. If it does, increment the currentLength.
7. Once the while loop finishes (the sequence breaks), update longest with the maximum of longest and currentLength.
8. Return longest.

Solution

/**
 * @param {number[]} nums
 * @return {number}
 */
function longestConsecutive(nums) {
    const set = new Set(nums);
    let longest = 0;
    
    for (let num of set) {
        // Only start counting if 'num' is the beginning of a sequence
        if (!set.has(num - 1)) {
            let currentLength = 1;
            
            // Keep checking for the next consecutive numbers
            while (set.has(num + currentLength)) {
                currentLength++;
            }
            
            longest = Math.max(longest, currentLength);
        }
    }
    
    return longest;
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the number of elements in nums. Creating the set takes $O(n)$. Although there is a while loop inside the for loop, the inner loop only runs for elements that are part of a sequence, and only starting from the first element of that sequence. This means every number is visited at most twice (once in the for loop, and at most once in the while loop). The overall operations scale linearly.
• Space Complexity: $O(n)$. The Hash Set stores exactly the unique elements from the array, which takes linear extra space.