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.

10/10/2015 udpate

use an unordered_set

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> set;
        for(int num: nums){
            set.insert(num);
        }
        int ans = 0;
        int count = 0;
        for(int num: set){
            //expand in two directions
            count = 1;
            //set.erase(num); DO NOT ERASE THE CURRENT ITERATOR!
            int i = 1;
            while(set.count(num + i) > 0){
                set.erase(num + i);
                count++;
                i++;
            }
            i = 1;
            while(set.count(num - i) > 0){
                set.erase(num - i);
                count++;
                i++;
            }
            ans = max(ans, count);
        }
        return ans;
    }
};

AC by one time.

First, it’s obvious to figure out an o(nlogn) algorithm by sort the array and count the consecutive numbers.

Second, the problem requires us to use an o(n) algorithm, so we must use more space than quick sort.

Using a hash table is a good choice.

//Ask the interviewer:
//can nums be empty?
//can nums contains duplicate elements?
//can I manipulate nums array?
//O(n) in time and space complexity?
//
//O(nlogn) in time is obvious, sort the array and count the consecutive numbers.
//so I should use more space to compensate time.
//
//How about using a hash table?
//
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int max = 0;
        int thisMax = 0;
        unordered_map<int, int> map;
        for(auto it = nums.begin(); it != nums.end(); it++){
            map[*it] = 1;
        }
        for(auto it = nums.begin(); it != nums.end(); it++){
            if(map.find(*it) != map.end()){
                thisMax = 1;
                map.erase(*it);
                for(int i = 1; map.find(*it - i) != map.end(); i++){
                    thisMax++;
                    map.erase(*it - i);
                }
                for(int i = 1; map.find(*it + i) != map.end(); i++){
                    thisMax++;
                    map.erase(*it + i);
                }
                if(thisMax > max){
                    max = thisMax;
                }
            }
        }
        return max;
    }
};