Longest Consecutive Sequence

 Problem:

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.

Solution:
class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int size = num.size();
        int count = 1, count_so_far = 1;
        sort(num.begin(), num.end());
        for (int i = 0; i < size; i++) {
            if (num[i+1] == num[i] + 1) {
                count_so_far++;
                count = (count_so_far > count ? count_so_far : count);
            } else if (num[i+1] != num[i]) {
                count_so_far = 1;
            }
        }
        return count;
    }
};

======= Second time ===== without sort ======

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> st;
        for (int i = 0; i < nums.size(); i++) {
            st.insert(nums[i]);
        }
        set<int>::iterator it = st.begin();
        int sol = 0, ans = 1, prev = 0;
        while (it != st.end()) {
            if (it != st.begin()) {
                if (*it - prev == 1) {
                   ans++;
                } else {
                    ans = 1;
                }
            }
            sol = max(sol, ans);
            prev = *it;
            it++;
        }    
        return sol;
    }
};

======= using unordered stl =========
http://yucoding.blogspot.com/2013/05/leetcode-question-129-longest.html

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int ans = 0;
        if (nums.size() == 0) {
            return ans;
        }
     
        unordered_map<int, bool> mp;
        for (auto val : nums) {
            mp[val] = true;
        }
     
        for (auto val : nums) {
            int count = 1;
            int num = val;
            if (mp.find(num) == mp.end()) {
                ans = max(ans, count);
                continue;
            }
            mp.erase(num);
            while (mp.find(num + 1) != mp.end()) {
                count++;
                mp.erase(num + 1);
                num++;
            }
         
            num = val;
            while (mp.find(num - 1) != mp.end()) {
                count++;
                mp.erase(num - 1);
                num--;
            }
         
            ans = max(ans, count);
        }
        return ans;
    }
};

============== Map ========
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        map<int, bool> mp;
        for (int num : nums) {
            mp[num] = false;
        }
     
        int ans = 0;
        for (int num : nums) {
            int count = 0;
            if (mp[num]) {
                continue;
            }
            int temp = num;
            while (true) {
                if (mp.find(num) == mp.end() ||
                   mp[num]) {
                    break;
                }
                mp[num] = true;
                count++;
                num--;
            }
            num = temp + 1;
            while (true) {
                if (mp.find(num) == mp.end() ||
                   mp[num]) {
                    break;
                }
                mp[num] = true;
                count++;
                num++;
            }
            ans = max(ans, count);
        }
     
        return ans;
    }
};

===================== Another attempt =======
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        set<int> st;
        for (auto num : nums) {
            st.insert(num);
        }
        int ans = 0;
       
        for (auto num : nums) {
            if (!st.count(num)) {
                continue;
            }
            int count = 0;
            int temp = num;
            while (st.count(temp)) {
                st.erase(temp);
                count++;
                temp++;
            }
            int temp2 = --num;
            while (st.count(temp2)) {
                st.erase(temp2);
                count++;
                temp2--;
            }
            ans = max(ans, count);
        }
        return ans;
    }
};