longest consecutive sequence

longest_consecutive_sequence.cpp

/*
 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. 
*/
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        int N = num.size();
        
        if (N <= 0)
            return 0;
        
        if (N == 1)
            return 1;
            
        set<int> sInt;
        for(int i=0; i<N; i++) 
            sInt.insert(num[i]);
        
        set<int>::iterator it = sInt.begin();
        int length = 1; 
        int prev = *it;
        int maxLen = length;
        while (it != sInt.end() ) {
            if ( *it - prev == 1 )
                length ++; 
            else  {
                maxLen = max(maxLen, length);
                length = 1; // it itself
            }
            
            prev = *it;
            ++it;
        }
        maxLen = max(maxLen, length);   //in case its always increasing
        return maxLen;
        
        
        /* In above case, if considering set.insert(*) is only amortized to const,  but usually O(logn),
            It's not absoluately o(n) algorithm.
            Another idea is to insert to a hash, then search from min, to min+1, min+2 ...
              This will work for many data points, not a few of them.
        //build a hash table, and find min / max
        //from min, try to get min+1, min+2 ... from hash, until max
        int N = num.size();
        int m = INT_MAX, M = INT_MIN;
        unordered_set<int> hash;
        // build hash
        for(int i=0; i<N; i++) {
            m = min(m, num[i]);
            M = max(M, num[i]);
            hash.insert(num[i]);
        }
        
        // search from hash
        int scan = m;
        int length = 1; //scan itself
        int maxLen = 1;
        while (scan <= M ) {
            while( scan + 1 <=M && hash.find(scan+1) != hash.end() ) {
                scan ++;
                length ++;
                if (scan > 0 && scan+1 < 0)
                break;
            }
            // now scan+1 is not included, remember the length
            maxLen = max(maxLen, length);
            
            //get next included element
            while (scan+1 <=M && hash.find(scan+1) == hash.end() )  {
                if (scan > 0 && scan+1 < 0)
                    break;
                scan ++;
            }
            
            //now scan+1 is included
            scan ++;
            length = 1; // scan itself
            if (scan >0 && scan+1 < 0  )     //overflow
                break;
        }
        
        return maxLen;
        */
    }
};