To find the longest sequence of consecutive integers in an unsorted array with O(n) time complexity, use the following approach:

1. Insert all elements into an unordered_set, which prvoides average O(1) lookup time and atuomatically removes duplicates.
2. Iterate through each number in the set. Only start counting a sequence if the current number is the beginning of a sequence—that is, when num - 1 is not present in the set.
3. For such starting numbers, incrementally check for num + 1, num + 2, etc., to determine the full length of the consecutive sequence.
4. Track and update the maximum sequence length encountered.

This ensures each element is processed at most twice—once during the initial iteration and once during sequence expansion—keeping the total time complexity linear.

Here's a clean implementation in C++:

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> numSet(nums.begin(), nums.end());
    int maxLength = 0;

    for (int val : numSet) {
        // Only start counting if val is the first in its sequence
        if (numSet.count(val - 1) == 0) {
            int current = val;
            int length = 1;

            while (numSet.count(current + 1)) {
                current++;
                length++;
            }

            maxLength = max(maxLength, length);
        }
    }

    return maxLength;
}

Key points:

• unordered_set::count(x) returns 1 if x exists, 0 otherwise—simpler than using find() and comparing to end().
• The condition numSet.count(val - 1) == 0 ensures we only process the smallest number of each consecutive block, avoiding redundant work.
• Duplicates are automatically handled by the set’s uniqueness property.

Example test cases:

• Input: {100, 4, 200, 1, 3, 2} → Output: 4 (sequence: 1–4)
• Input: {0, 3, 7, 2, 5, 8, 4, 6, 0, 1} → Output: 9 (sequence: 0–8)
• Edge cases like empty or single-element arrays correctly return 0 or 1.

The algorithm efficiently leverages hash-based lookups and smart traversal to achieve optimal performance without sorting.