Longest Consecutive Sequence medium

Problem Statement

Given an unsorted array of integers nums, find the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

Example 1:

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.

Example 2:

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

Steps:

1. Create a Set: Convert the input array nums into a Set. This allows for O(1) lookup time, crucial for achieving O(n) overall complexity.

2. Iterate and Check: Iterate through each number num in the Set.

3. Check for Start of Sequence: For each number, check if it's the start of a consecutive sequence by verifying that num - 1 is not present in the Set. This ensures we only start counting sequences from their beginning.

4. Extend Sequence: If it's the start of a sequence, start counting. Increment num repeatedly, checking if each subsequent number is in the Set. The count continues until a number is not found in the set.

5. Update Maximum: Keep track of the maximum length found so far and update it whenever a longer sequence is discovered.

Explanation:

The key to achieving O(n) time complexity is using a Set. A naive approach that involves sorting would take O(n log n) time. By using a Set, we can check for the existence of a number in constant time. We only need to iterate through the array once (or the set once which is the same). For each number, we explore its potential consecutive sequence only if it's the starting point of a new sequence; otherwise, it's already been accounted for in a previous iteration.

Code:

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

    for (const num of numSet) {
        if (!numSet.has(num - 1)) { // Check if it's the start of a sequence
            let currentNum = num;
            let currentStreak = 1;

            while (numSet.has(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
};

Complexity:

• Time Complexity: O(n) - We iterate through the set once. While the inner while loop might seem problematic, it only executes once for each starting point of a consecutive sequence. The total number of iterations of the inner loop is therefore proportional to the size of the input (n).

• Space Complexity: O(n) - The space is dominated by the Set which stores the input numbers. In the worst-case scenario, all numbers are unique, thus requiring O(n) space.