Longest Consecutive Sequence Solutions in C++

// Source : https://oj.leetcode.com/problems/longest-consecutive-sequence/
// Author : Hao Chen
// Date   : 2014-06-22



//
//  Obviously, the easist way is sort the array, however the run-time complexity is O(nlogn)
//  
//  If we cannot use the sort algorithm, then it seems we have to use O(n^2) solution.
//
//  That's fine, let's take a look the O(n^2) soultion
//
//      1) for each item num[i] in the array
//      2) for loop to seach ...... num[i-2], num[i-1],  num[i]+1, num[i]+2 ......
//  
//  We can see, the search is really heavy, and the best data structure for seaching is HashMap.
//  hash map is O(1) run-time complexity for seaching.
//
//  So, we can have the following solution by using Hash Map.
//   

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        
        map<int, int> m;
        for (int i=0; i<num.size(); i++){
            m[num[i]]=i;
        }
        
        int max_seq=0; 
        for (int i=0; i<num.size(); i++){
            int cnt=1;
            
            for(int n = num[i]+1;m.find(n)!=m.end();n++){
                m.erase(m.find(n));
                cnt++;
                
            }
            for(int n = num[i]-1;m.find(n)!=m.end();n--){
                m.erase(m.find(n));
                cnt++;
            }
            if (max_seq < cnt){
                max_seq = cnt;
            }
            if (m.size()==0){
                break;
            }
        }
        return max_seq;
    }
};

#include <vector>
#include <unordered_map>
using std::vector; using std::unordered_map;

class Solution {
public:
    int longestConsecutive(vector<int> &num) {
        unordered_map<int, int> map;
        int max{0};
        for (auto i : num)
            if (!map[i]) {
                map[i] = map[i+1] + map[i-1] + 1;
                map[i-map[i-1]] = map[i+map[i+1]] = map[i];
                max = std::max(max, map[i]);
            }
        return max;
    }
};

/// Source : https://leetcode.com/problems/longest-consecutive-sequence/description/
/// Author : liuyubobobo
/// Time   : 2017-11-03

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/// Sort
/// Remove duplicate elements and get result
///
/// Time Complexity: O(nlogn)
/// Space Complexity: O(1)
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {

        if(nums.size() == 0)
            return 0;

        sort(nums.begin(), nums.end());
        int len = 0;
        for(int start = 0, i = start + 1 ; i <= nums.size() ; ){
            if(i == nums.size() || nums[i] != nums[start]){
                nums[len++] = nums[start];
                start = i;
                i = start + 1;
            }
            else
                i ++;
        }

//        printVec(nums);
//        cout << "len = " << len << endl;

        int res = 1;
        for(int start = 0, i = start + 1 ; i <= len ;){
            if(i == nums.size() || nums[i-1] + 1 != nums[i] ){
                res = max(res, i-start);
                start = i;
                i = start + 1;
            }
            else
                i ++;
        }

        return res;
    }

private:
    void printVec(const vector<int>& vec){
        for(int e: vec)
            cout << e << " ";
        cout << endl;
    }
};

int main() {

    int nums1[6] = {100, 4, 200, 1, 3, 2};
    vector<int> vec1(nums1, nums1 + sizeof(nums1)/sizeof(int));
    cout << Solution().longestConsecutive(vec1) << endl;
    // 4

    // ---

    int nums2[4] = {1, 2, 0, 1};
    vector<int> vec2(nums2, nums2 + sizeof(nums2)/sizeof(int));
    cout << Solution().longestConsecutive(vec2) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/longest-consecutive-sequence/description/
/// Author : liuyubobobo
/// Time   : 2017-11-03

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/// Sort
/// Remove duplicate elements on the fly
///
/// Time Complexity: O(nlogn)
/// Space Complexity: O(1)
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {

        if(nums.size() == 0)
            return 0;

        sort(nums.begin(), nums.end());

        int res = 1;
        int curres = 1;
        for(int i = 1 ; i <= nums.size() ; i ++){
            if(i == nums.size() || nums[i] - nums[i-1] > 1 ){
                res = max(res, curres);
                curres = 1;
            }
            else if(nums[i-1] + 1 == nums[i])
                curres ++;

        }

        return res;
    }
};

int main() {

    int nums1[6] = {100, 4, 200, 1, 3, 2};
    vector<int> vec1(nums1, nums1 + sizeof(nums1)/sizeof(int));
    cout << Solution().longestConsecutive(vec1) << endl;
    // 4

    // ---

    int nums2[4] = {1, 2, 0, 1};
    vector<int> vec2(nums2, nums2 + sizeof(nums2)/sizeof(int));
    cout << Solution().longestConsecutive(vec2) << endl;
    // 3

    return 0;
}

/// Source : https://leetcode.com/problems/longest-consecutive-sequence/description/
/// Author : liuyubobobo
/// Time   : 2017-11-03

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

/// Using Set
///
/// Time Complexity: O(n)
/// Space Complexity: O(n)
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {

        if(nums.size() == 0)
            return 0;

        unordered_set<int> unique_nums(nums.begin(), nums.end());

        int res = 1;
        for(int num: unique_nums) {
            if(unique_nums.find(num - 1) == unique_nums.end()){
                int offset = 1;
                while(unique_nums.find(num + offset) != unique_nums.end())
                    offset ++;
                res = max(res, offset);
            }
        }

        return res;
    }
};

int main() {

    int nums1[6] = {100, 4, 200, 1, 3, 2};
    vector<int> vec1(nums1, nums1 + sizeof(nums1)/sizeof(int));
    cout << Solution().longestConsecutive(vec1) << endl;
    // 4

    // ---

    int nums2[4] = {1, 2, 0, 1};
    vector<int> vec2(nums2, nums2 + sizeof(nums2)/sizeof(int));
    cout << Solution().longestConsecutive(vec2) << endl;
    // 3

    return 0;
}