leetcode Question 129: Longest Consecutive Sequence

Longest Consecutive Sequence

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.

Analysis:

At first glance, the "longest" requirement may lead us to DP. But this problem actually tests data structure rather than a certain algorithm.

If there is no O(n) requirement, we can just sort the array (O(n log n)), then find then longest sequence after a scan.

With the time limit O(n), first of all, what comes to my mind is HASH MAP! Because hash map searches value by key in O(1) time. Note that in C++ STL, the map<> data structure is implemented by BST, so the insert in O(log n), therefore we need to use the unordered_map<>, which has O(1) time complexity.

Firstly, we put all the element into a map.
Secondly, how to find the consecutive elements? Since the O(n) requirement, scan the array is a must.
For each element, we need to find its consecutive elements. Consecutive means +1 or -1, a while loop is enough to handle. Search two directions respectively (+1, -1),  during the search if the key is found, remove the current item in the map. This is because if two items are consecutive, the longest elements for this two are the same, no need to search again. In this way, the length of longest consecutive elements can be easily found.

Note that in C++ map<>, find(key) function will return  the end() iterator if key does not exist, But if we use (mp[key]==false), when key is not in the map, the program will insert the key into the map with a default value, so use find function is a safer way.

Code (C++):

class Solution {
public:

    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unordered_map<int,bool>mp;
        for (int i=0;i<num.size();i++){
            mp[num[i]]=true;
        }
        
        int res=0;
        for (int i=0;i<num.size();i++){
            int mx=1;      
            int fd = num[i];
            
            mp.erase(num[i]);
            while (mp.find(fd+1)!=mp.end()){
                mx++;
                mp.erase(fd+1);
                fd++;
            }
            
            fd = num[i];
            while (mp.find(fd-1)!=mp.end()){
                mx++;
                mp.erase(fd-1);
                fd--;
            }
            
            if (mx>res){res=mx;}
        }
        
        return res;
    }
};

Code(Python):

class Solution:
    # @param num, a list of integer
    # @return an integer
    def longestConsecutive(self, num):
        dic = {}
        maxlen = 1
        for n in num:
            dic[n] = 1
        for n in num:
            if dic.has_key(n):
                tmp = n + 1
                l = 1
                while dic.has_key(tmp):
                    l+=1
                    del dic[tmp]
                    tmp+=1
                tmp = n - 1
                while dic.has_key(tmp):
                    l+=1
                    del dic[tmp]
                    tmp-=1
                maxlen = max(l, maxlen)
            else:
                continue
        return maxlen