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 HashSet: Insert all numbers from the input array nums into a HashSet. HashSets provide O(1) average time complexity for insertion and lookup.

2. Iterate and Check: Iterate through the nums array. For each number num:

   • Check if the number is the start of a sequence (meaning num - 1 is not present in the HashSet).
   • If it's the start of a sequence, start counting the consecutive numbers. Keep incrementing num and checking its presence in the HashSet until a number is not found.
   • Update the longestStreak variable if the current streak is longer.

3. Return the Result: After iterating through all numbers, return the longestStreak.

Explanation:

The key to achieving O(n) time complexity is using a HashSet. A naive approach of sorting the array would take O(n log n) time. By using a HashSet, we can quickly check if a number is present or absent in constant time on average. We only need to iterate through the array once (O(n)), and for each number, we perform a constant-time check in the HashSet. The nested loop within the sequence checking isn't actually O(n^2) because each number is only examined once as the "start" of a potential sequence.

Code:

#include <iostream>
#include <unordered_set>

using namespace std;

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> num_set;
    for (int num : nums) {
        num_set.insert(num);
    }

    int longestStreak = 0;
    for (int num : nums) {
        if (num_set.find(num - 1) == num_set.end()) { // Check if it's the start of a sequence
            int currentNum = num;
            int currentStreak = 1;

            while (num_set.find(currentNum + 1) != num_set.end()) {
                currentNum++;
                currentStreak++;
            }

            longestStreak = max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
}

int main() {
    vector<int> nums1 = {100, 4, 200, 1, 3, 2};
    cout << "Longest consecutive sequence length for nums1: " << longestConsecutive(nums1) << endl; // Output: 4

    vector<int> nums2 = {0, 3, 7, 2, 5, 8, 4, 6, 0, 1};
    cout << "Longest consecutive sequence length for nums2: " << longestConsecutive(nums2) << endl; // Output: 9

    return 0;
}

Complexity:

• Time Complexity: O(n) - We iterate through the array once, and HashSet operations are O(1) on average.
• Space Complexity: O(n) - In the worst case, the HashSet could store all the numbers from the input array.