Longest Consecutive Sequence

An unsorted array of integers is provided, and the goal is to find the length of the longest sequence of consecutive elements. The elements do not need to be contiguous in the original array layout, but when selected and reordered, they must form an unbroken consecutive integer chain ($x, x+1, x+2, \dots$).

Input:  a = [102, 4, 100, 1, 101, 3, 2, 1, 1]
Output: 4
Explanation: The longest consecutive sequence is [1, 2, 3, 4].

1. Problem Understanding & Naive Intuition

The fundamental challenge requires identifying contiguous numeric runs within an unsorted array that may contain duplicates and arbitrarily ordered values.

Consider the sample array: [102, 4, 100, 1, 101, 3, 2, 1, 1]

We can observe multiple sequence fragments:

• Sequence starting at 100: [100, 101, 102] $\rightarrow$ Length = $3$
• Sequence starting at 1: [1, 2, 3, 4] $\rightarrow$ Length = $4$

The required answer is the length of the maximum valid sequence, which is 4.

Key Rule: Duplicate elements (e.g., multiple occurrences of 1 or 2) do not extend sequence lengths. They must be ignored during consecutive length evaluation.

2. Core Mental Model: "Sequence Start Identification"

To avoid redundant computations, every consecutive sequence can be uniquely identified by its starting element.

An element $x$ is the starting element of a sequence if and only if $x - 1$ does not exist in the array.

By identifying starting elements first, we avoid launching sequence checks from the middle of a chain.

3. Brute Force Approach: Linear Search Driven Exploration

Conceptual Idea

For every element $x$ in the array:

1. Assume $x$ is a potential sequence start and set count = 1.
2. Perform a linear search across the entire array for $x + 1$.
3. If $x + 1$ is found, increment $x \leftarrow x + 1$ and count $\leftarrow$ count + 1.
4. Repeat searching for the next sequential value until linear search fails.
5. Update the global maximum length.

Algorithm Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool linearSearch(const vector<int>& a, int num) {
    int n = a.size();
    for (int i = 0; i < n; i++) {
        if (a[i] == num) return true;
    }
    return false;
}

int longestSuccessiveElementsBrute(vector<int>& a) {
    int n = a.size();
    if (n == 0) return 0;

    int longest = 1;

    for (int i = 0; i < n; i++) {
        int x = a[i];
        int count = 1;

        // Keep searching for consecutive elements via linear search
        while (linearSearch(a, x + 1) == true) {
            x = x + 1;
            count = count + 1;
        }

        longest = max(longest, count);
    }
    return longest;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N^2)$ in the worst/average case. For each element $N$, we perform linear searches across $N$ elements.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space as no additional data structures are required.

4. Better Approach: Sorting & Single-Pass Traversal

Intuition

If the array is sorted, elements belonging to the same consecutive sequence will land adjacent to each other.

Original Array: [102, 4, 100, 1, 101, 3, 2, 1, 1]
Sorted Array:   [1, 1, 1, 2, 2, 3, 3, 4, 100, 101, 101, 102]

State Variables

To process duplicates and breaks correctly in a single pass, track three variables:

1. lastSmaller: Stores the value of the previously included valid sequence element (initialized to INT_MIN).
2. cnt: Tracks the length of the current active consecutive sequence (initialized to 0).
3. longest: Stores the maximum sequence length seen so far (initialized to 1).

Traversal Rules

For each element arr[i]:

• Case 1: Consecutive Element (arr[i] - 1 == lastSmaller) The current element continues the sequence. Increment cnt by 1 and update lastSmaller = arr[i].
• Case 2: Duplicate Element (arr[i] == lastSmaller) The current element is identical to the previous element. Ignore it to prevent incorrect counts.
• Case 3: Sequence Break (arr[i] != lastSmaller) The current element cannot extend the current sequence. Start a new sequence: reset cnt = 1 and update lastSmaller = arr[i].

5. Walkthrough & Code: Better Approach

Step-by-Step Execution Trace

Sorted Input: [1, 1, 2, 3, 4, 100, 101, 102]

Implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int longestSuccessiveElementsBetter(vector<int>& a) {
    int n = a.size();
    if (n == 0) return 0;

    // Sort the array: O(N log N)
    sort(a.begin(), a.end());

    int lastSmaller = INT_MIN;
    int cnt = 0;
    int longest = 1;

    for (int i = 0; i < n; i++) {
        if (a[i] - 1 == lastSmaller) {
            // Continuation of current consecutive sequence
            cnt += 1;
            lastSmaller = a[i];
        } 
        else if (a[i] != lastSmaller) {
            // Sequence break: Reset counter for new sequence
            cnt = 1;
            lastSmaller = a[i];
        }
        // If a[i] == lastSmaller, do nothing (ignore duplicate)

        longest = max(longest, cnt);
    }

    return longest;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N \log N) + \mathcal{O}(N) = \mathcal{O}(N \log N)$ due to sorting.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space if in-place sorting like $O(1)$ space intro-sort is used.

6. Optimal Approach: Hash Set Lookup Strategy

To achieve linear time complexity ($\mathcal{O}(N)$), array sorting must be eliminated. We achieve $O(1)$ average-time lookups using an Unordered Set (unordered_set in C++ / HashSet in Java).

Structural Workflow

7. The First Element Optimization Logic

Without filtering out non-starting sequence elements, the set lookup would degrade back to $\mathcal{O}(N^2)$ work.

Counter-Example (Without Optimization):

Suppose the sequence is [1, 2, 3, 4].

• Check 1 $\rightarrow$ count 1, 2, 3, 4 (4 lookups)
• Check 2 $\rightarrow$ count 2, 3, 4 (3 lookups)
• Check 3 $\rightarrow$ count 3, 4 (2 lookups)
• Check 4 $\rightarrow$ count 4 (1 lookup)

Total lookups: $4 + 3 + 2 + 1 = 10 \approx \mathcal{O}(N^2)$.

With First Element Optimization:

• Check 1: 0 is NOT in set $\rightarrow$ START! Count 1, 2, 3, 4 (4 lookups).
• Check 2: 1 IS in set $\rightarrow$ SKIP! (0 lookups).
• Check 3: 2 IS in set $\rightarrow$ SKIP! (0 lookups).
• Check 4: 3 IS in set $\rightarrow$ SKIP! (0 lookups).

Total lookups: $4 \approx \mathcal{O}(N)$. Each element is processed at most twice across the entire execution.

8. Optimal Solution Implementation

C++ Source Code

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

using namespace std;

int longestSuccessiveElementsOptimal(const vector<int>& a) {
    int n = a.size();
    if (n == 0) return 0;

    int longest = 1;
    unordered_set<int> st;

    // Step 1: Insert all array elements into unordered_set: O(N) average
    for (int i = 0; i < n; i++) {
        st.insert(a[i]);
    }

    // Step 2: Iterate through elements in the set
    for (auto it : st) {
        // Check if current element 'it' is the starting element of a sequence
        if (st.find(it - 1) == st.end()) {
            int cnt = 1;
            int x = it;

            // Search for consecutive elements x+1, x+2...
            while (st.find(x + 1) != st.end()) {
                x = x + 1;
                cnt = cnt + 1;
            }

            longest = max(longest, cnt);
        }
    }

    return longest;
}

9. Complexity & Production Edge Cases

Time Complexity Derivation

1. Set Insertion: Inserting $N$ elements into an unordered_set takes $\mathcal{O}(N)$ on average.
2. Set Iteration: Iterating over $N$ unique elements takes $\mathcal{O}(N)$.
3. Inner While Loop: The while loop runs only for sequence starting elements. Across all sequences, the loop runs a total of $N$ times across the entire program runtime.

Production Edge Case (Hash Collisions): In C++ std::unordered_set, if hash collisions occur repeatedly (due to poorly distributed keys or tailored test cases), lookup performance degrades from $\mathcal{O}(1)$ to $\mathcal{O}(N)$. Under severe collision scenarios, total time complexity becomes $\mathcal{O}(N^2)$. If strict upper bounds are required without collision risks, the sorting approach ($\mathcal{O}(N \log N)$) can be preferable.

Space Complexity

• Auxiliary Space: $\mathcal{O}(N)$ to store array values in the hash set.

10. Comprehensive Comparison Matrix

Summary and Key Takeaways

• Problem Requirement: Find the longest sequence of numerically consecutive integers, order-agnostic, ignoring duplicates.
• Brute Force Failure: Searching for $x+1$ via linear search results in inefficient $\mathcal{O}(N^2)$ running time.
• Sorting Efficiency: Sorting groups consecutive values together, enabling linear detection in $\mathcal{O}(N \log N)$ overall time.
• Set Optimization: Storing unique array elements in an unordered_set reduces lookups to $\mathcal{O}(1)$ average time.
• Sequence Start Condition: Checking if $(x - 1)$ exists ensures sequence lookups run only from true sequence starting nodes.
• Overall Optimal Runtime: Average time complexity drops to $\mathcal{O}(N)$ with $\mathcal{O}(N)$ extra space usage.