Find the longest sequence of consecutive numbers

Given an unsorted array with only distinct elements, find the length of the longest sequence of consecutive numbers in the array.

Example Test Cases

Sample Test Case 1

Array: 0, 7, 2, 1, 6, 5, 3
Expected Output: 4
Explanation: There are only two possible subsequences with consecutive elements [5, 6, 7 ] and [0, 1, 2, 3] . The 2^nd one has larger length 4.

Sample Test Case 2

Array: 2, 4, 6, 8, -1
Expected Output: 1
Explanation: Each element can be considered a consecutive element sequence of length 1.

Solution

The core idea is that each number in the array, can either be start of some consecutive sequence or it can be a part of some already existing sequence.

If it is a start of some sequence, we will simulate the whole process of counting all the numbers. for example, if the number which is start of sequence is 5 then we will check for the existence of 6 then 7 and so on.

If it is not a part of some sequence, then we will ignore the number.

We can implement the above solution by maintaining a Hash table corresponding to all the distinct elements in the array. We will first insert all the numbers into the hash table and then if any corresponding number can be a starting number for a new consecutive sequence, we will compute the length of that sequence.

See the code below for implementation

Implementation

#include <bits/stdc++.h>

using namespace std;

int main() {
    vector v = { 0, 7, 2, 1, 6, 5, 3 };
    unordered_map<int, bool=""> mp;
    for(int i = 0; i < v.size(); i++) {
        mp[v[i]] = true;
    }
    int maxLen = 1;
    for(int i = 0; i < v.size(); i++) {
        // Since v[i] - 1 doesn't exist, it can be a start of some consecutive sequence.
        if (mp.find(v[i] - 1) == mp.end()) {
            int length = 1;
            auto it = mp.find(v[i] + 1);
            while (it != mp.end()) {
                length++;
                it = mp.find(v[i] + length);
            }
            maxLen = max(maxLen, length);
        }
    }

    cout << " Maximum length = " << maxLen << "\n";

    return 0;
}

Time Complexity

Since each element will be counted at most two times as a part of either outer loop or inner while loop, the total complexity of the solution would be O(n)