Find the longest sequence of consecutive numbers

Companies:
  • Amazon Interview Questions
  • Microsoft Interview Questions

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 2nd 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)

Scroll to Top