Longest Consecutive Sequence medium

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 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 HashSet: A HashSet (or similar data structure providing O(1) average-case lookup) is used to store the numbers from the input array. This allows for fast checking if a number exists.

2. Iterate through the array: For each number in the input array:

3. Check for the start of a sequence: Before processing a number, check if it's the potential start of a consecutive sequence. This means verifying if the number num - 1 is not present in the HashSet. If num -1 is present, it means this number is part of a sequence already being processed (to avoid double-counting).

4. Extend the sequence: If it's the start of a sequence, iterate upwards to find the length of the sequence. Keep incrementing the number (num + 1, num + 2, etc.) and check if it's present in the HashSet. Count the length of this sequence.

5. Update the maximum length: Keep track of the maximum length encountered so far.

6. Return the maximum length: After iterating through all numbers, return the maximum length found.

Explanation:

The key optimization is using a HashSet. A naive approach might involve sorting the array (O(n log n)), then iterating to find the longest sequence. The HashSet allows us to check for the presence of a number in constant average-case time, bringing the overall time complexity down to O(n). We only need to explore each number once as we efficiently identify the start of a consecutive sequence.

Code:

using System;
using System.Collections.Generic;

public class Solution {
    public int LongestConsecutive(int[] nums) {
        HashSet<int> numSet = new HashSet<int>(nums); // O(n) to insert
        int longestStreak = 0;

        foreach (int num in nums) {
            if (!numSet.Contains(num - 1)) { // Check if this is the start of a sequence
                int currentNum = num;
                int currentStreak = 1;

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

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

        return longestStreak;
    }
}

Complexity:

• Time Complexity: O(n) - We iterate through the array once. While the inner while loop might seem problematic, it only executes for elements that are not at the start of a consecutive sequence. Therefore the overall number of iterations remains linear with respect to the input size. HashSet lookups are O(1) on average.

• Space Complexity: O(n) - The HashSet stores all the numbers from the input array. In the worst case, all numbers are unique, resulting in O(n) space usage.