[Leetcode] 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:

1. Take [100, 4, 200, 1, 3, 2] as an example 
2. First, for 100, we look for 101, 102 ... and 99, 98... in the array. If the number exist, add count and mark it as visited
3. Next, if next number (4) was not visited, do the same as step 2
4. Loop until end of the array

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        map<int, bool> m;
        for(int i=0; i<num.size(); i++)
        {
            m[num[i]] = false;
        }
        
        int maxCount = 0;
        for(int i=0; i<num.size(); i++)
        {
            //the num was not visited
            if (m.find(num[i]) != m.end() && !m[num[i]])
            {
                int n = num[i]-1;
                int count = 1;
                while(m.find(n) != m.end() && !m[n])
                {
                    m[n] = true;
                    n--;
                    count++;
                }
                
                n = num[i] + 1;
                while(m.find(n) != m.end() && !m[n])
                {
                    m[n] = true;
                    n++;
                    count++;
                }
                
                maxCount = max(maxCount, count);
            }
        }
        
        return maxCount;
    }
};