 # 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 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