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)`