Understanding the Problem

Given an array of integers, a consecutive sequence is a sequence of numbers where each consecutive number appear exactly once. The task is to identify the longest consecutive sequence in the array and determine its length.

Examples

Example 1:

Input: arr[] = {100, 4, 200, 1, 3, 2}

Output: Length of Longest Consecutive Sequence: 4

Explanation: The longest consecutive sequence is [1, 2, 3, 4]

Different Approaches

1 Brute Force Approach

• Generate all possible consecutive sequences from the array and find the length of each sequence.

Code:

#include <bits/stdc++.h>
using namespace std;

bool linearSearch(vector<int>&a, int num) {
    int n = a.size(); //size of array
    for (int i = 0; i < n; i++) {
        if (a[i] == num)
            return true;
    }
    return false;
}
int longestSuccessiveElements(vector<int>&a) {
    int n = a.size(); //size of array
    int longest = 1;
    //pick a element and search for its
    //consecutive numbers:
    for (int i = 0; i < n; i++) {
        int x = a[i];
        int cnt = 1;
        //search for consecutive numbers
        //using linear search:
        while (linearSearch(a, x + 1) == true) {
            x += 1;
            cnt += 1;
        }

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

int main()
{
    vector<int> a = {100, 200, 1, 2, 3, 4};
    int ans = longestSuccessiveElements(a);
    cout << "The longest consecutive sequence is " << ans << "\n";
    return 0;
}

// Output
The longest consecutive sequence is 4

Complexity Analysis:

Time Complexity: O(N ^ 2), N = size of the array.

• We are using nested loops each running for approximately N times.

Space Complexity: O(1)

2 Better Approach (Using Sorting)

We can simply sort the array and run a for loop to find the longest consecutive sequence.

3 Optimal Approach (Using Set data structure)

1. Store all elements of the array in a HashSet for efficient lookup.
2. For each element in the array, check if its consecutive elements exist in the HashSet and count the lenght of the consecutive sequence.

Code:

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

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> numSet(nums.begin(), nums.end());
    int longestSeq = 0;
    for (int num : numSet) {
        if (!numSet.count(num - 1)) {
            int currentNum = num;
            int currentSeq = 1;
            while (numSet.count(currentNum + 1)) {
                currentNum++;
                currentSeq++;
            }
            longestSeq = max(longestSeq, currentSeq);
        }
    }
    return longestSeq;
}

int main() {
    vector<int> nums = {100, 4, 200, 1, 3, 2};
    cout << "Length of Longest Consecutive Sequence: " << longestConsecutive(nums) << endl;
    return 0;
}

// Output
Length of Longest Consecutive Sequence: 4

Complexity Analysis:

Time Complexity: O(n)

• Constructing the HashSet from the input array takes O(n) time, where n is the number of elements in the array.
• Traversing the array once, O(n)
• Overall, O(n) + O(n) = O(n)

Space Complexity: O(n)