Problem description:

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

Your algorithm should run in O(n) complexity.

Example:

1
2
3
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Solution:

The idea is, when we have a number n, check it’s n+1 and n-1 to get the maximum length, and erase them from the set. Because if they’re consecutive, only need to count once.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.empty()) return 0;
        unordered_set<int> record(nums.begin(), nums.end());
        int res= 1;
        for(auto n: nums){
            if(!record.count(n)) continue;
            record.erase(n);
            
            //use two pointer search toward left and right to find the largest range
            int left= n-1, right= n+1;
            while(record.count(left)) record.erase(left--);
            while(record.count(right)) record.erase(right++);
            
            res= max(res, right-left-1);
        }
        return res;
    }
};

time complexity: $O(n)$
space complexity: $O(n)$
reference: