[leetcode] 128 Longest Consecutive Sequence

/*

http://leetcode.com/onlinejudge#question_128

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.

*/

class Solution {
public:
    int longestConsecutive(vector<int> &A) {

        const size_t N = A.size();


        unordered_set<int> S;
        unordered_set<int>::iterator it;

        unordered_set<int> visited;

        for(size_t i = 0; i < N; ++i)
        {
            S.insert(A[i]);
        }

        int maxsubseq = 0;


        for(size_t i = 0; i < N; ++i)
        {
            if(visited.find(A[i]) != visited.end())
            {
                continue;
            }

            int curmax = A[i], curmin = A[i];

            while(S.end() != (it = S.find(curmax+1)))
            {
                S.erase(it);
                ++curmax;
                visited.insert(curmax);
            }

            while(S.end() != (it = S.find(curmin-1)))
            {
                S.erase(it);
                --curmin;
                visited.insert(curmin);
            }

            int subseq = curmax - curmin + 1;
            maxsubseq = max(maxsubseq, subseq);
        }
        return maxsubseq;
    }
};