The problem is:

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,

Given

`[100, 4, 200, 1, 3, 2]`

,the longest consecutive elements sequence is`[1, 2, 3, 4]`

. Return its length:`4`

.Your algorithm should run in \( O(n) \) complexity.

The most intuitive solution to this problem is sorting the array first, and then go through the sorted array and record the length of the longest consecutive sequence. However, the time complexity of this method is \(O(n \log n)\).

In order to get the \( O(n) \) complexity, we can pick up the first element in array(say `num[0]`

), and then check if `num[0]-1`

and `num[0]+1`

are in the array. If yes, iteratively check the upper/lower boundary of this sequence. Until the upper/lower boundaries never change, find a new element in the array that has not been accessed and start a new search.

In this solution, a hash table(`unordered_map`

in C++) is needed to record the accessibility of each element in the array. The keys to the hash table are the integeres in the array, and the values are bool - if the key has been accessed, then set to `false`

; otherwise set to `true`

. In average, checking the existence(in C++, the `find()`

of `unordered_map`

) of a key in the hash table costs constant time. Since we only access every element in the array(or hash table) for only one time, and the operations for each element only cost \(O(1)\) time, the time complexity of this method is \( O(n) \). And the space complexity is also \( O(n) \) due to the hash table.

Following is my C++ implementation.

class Solution { public: int longestConsecutive(vector&num) { unordered_map<int,bool> map; for(auto& x:num) map[x]=true; int start=num[0]; int end=num[0]; int max_len=1; int cnt=1; // items have been accessed int idx=1; while(cnt<=num.size()) { //cout<<"start="<<start<<", end="<<end<<endl; // TEST ONLY map[start]=false; map[end]=false; // Find the lower boundary unordered_map<int,bool>::iterator got=map.find(start-1); if(got!=map.end() && got->second) { start--; cnt++; } // Find the upper boundary got=map.find(end+1); if(got!=map.end() && got->second) { end++; cnt++; } if(max_len<end-start+1) max_len=end-start+1; if(!(map[start]||map[end])) { // If both start and end rich the boundaries, // find a new entry for them. while(idx<num.size() && map[num[idx]]==false) idx++; start=num[idx]; end=num[idx]; map[start]=false; cnt++; } } return max_len; } }; </pre>