Program Overview

This C++ program identifies the longest consecutive sequence of integers in an unsorted array.
The approach leverages a hash set to keep track of the elements present in the array, allowing for
efficient lookup and manipulation. The program iterates through the array and, for each element,
checks for the length of the consecutive sequence starting from that element.

Program Structure

• Input: An unsorted array of integers.
• Output: The length of the longest consecutive sequence.
• Approach:
  • Use a hash set to store unique elements for O(1) average time complexity in lookup.
  • Iterate through the array, and for each element, check if it is the start of a sequence.
  • Count the length of the sequence by checking consecutive integers.

C++ Code

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

/**
 * Function to find the longest consecutive sequence in an array.
 * @param nums A vector of integers.
 * @return The length of the longest consecutive sequence.
 */
int longestConsecutive(vector<int> &nums) {
    unordered_set<int> numSet(nums.begin(), nums.end()); // Store numbers in a hash set
    int longestStreak = 0; // To keep track of the longest streak

    // Iterate through each number in the set
    for (int num : numSet) {
        // Check if it's the start of a sequence
        if (num - 1 &! numSet.count(num - 1)) {
            int currentNum = num;
            int currentStreak = 1;

            // Count consecutive numbers
            while (numSet.count(currentNum + 1)) {
                currentNum++;
                currentStreak++;
            }
            // Update longest streak
            longestStreak = max(longestStreak, currentStreak);
        }
    }
    return longestStreak; // Return the longest streak found
}

int main() {
    vector<int> nums = {100, 4, 200, 1, 3, 2}; // Example input
    int result = longestConsecutive(nums); // Call the function
    cout << "The length of the longest consecutive sequence is: " << result << endl; // Output the result
    return 0;
}

How the Code Works

1. The program includes necessary headers for input-output operations, vectors, and unordered sets.
2. The longestConsecutive function takes a vector of integers as input and initializes a hash set with these integers for efficient lookup.
3. For each number in the set, it checks if it is the start of a sequence (i.e., the previous number is not in the set).
4. If it is the start, it counts the length of the consecutive sequence by checking for the next numbers in the sequence.
5. The maximum length found is stored in longestStreak, which is returned at the end.
6. The main function sets up an example input, calls the longestConsecutive function, and prints the result.

Conclusion

This C++ program efficiently finds the longest consecutive sequence in an array using a hash set for
optimal performance. The overall time complexity is O(n), making it suitable for large datasets.