# 128. Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

# Solution

Approach 1: Sorting.

Approach 2: Hash table.

Apporach 3: HashSet and Intelligent Sequence Building.

# Code (Python)

Approach 1:

Approach 2:

# Code (C++)

Approach 1:

// Sorting.
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        std::sort(nums.begin(), nums.end());
        int maxRes = 1;
        int prev = nums[0];
        int count = 1;
        for (int i = 1; i < n; ++i)
        {
            if (nums[i] - prev == 1)
            {
                count++;
                maxRes = std::max(maxRes, count);
                prev = nums[i];
            }
            else if (nums[i] != prev)
            {
                prev = nums[i];
                count = 1;
            }
        }
        return maxRes;
    }
};

Approach 2:

// Hash talbe.
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        unordered_map<int,int> umap;
        int maxRes = 1;
        for (int i = 0; i < n; ++i)
        {
            if (umap.find(nums[i]) != umap.end())
                continue;
            else
                umap[nums[i]] = nums[i];
            int max = nums[i];
            int min = nums[i];
            if (umap.find(nums[i]+1) != umap.end())
                max = umap[nums[i]+1];
            if (umap.find(nums[i]-1) != umap.end())
                min = umap[nums[i]-1];
            umap[min] = max;
            umap[max] = min;
            maxRes = std::max(maxRes, max - min + 1);
        }
        return maxRes;
    }
};
// Hash talbe (use the index instead of the value)
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        if (n == 0)
            return 0;
        unordered_map<int,int> umap;
        int maxRes = 1;
        for (int i = 0; i < n; ++i)
        {
            if (umap.find(nums[i]) != umap.end())
                continue;
            else
                umap[nums[i]] = i;
            int max = i;
            int min = i;
            if (umap.find(nums[i]+1) != umap.end())
                max = umap[nums[i]+1];
            if (umap.find(nums[i]-1) != umap.end())
                min = umap[nums[i]-1];
            umap[nums[min]] = max;
            umap[nums[max]] = min;
            maxRes = std::max(maxRes, nums[max] - nums[min] + 1);
        }
        return maxRes;
    }
};
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        if (n <= 1)
            return n;
        unordered_map<int,int> umap;
        int max = 0;
        for (int i = 0; i < n; ++i) {
            if (umap.find(nums[i]) != umap.end())
                continue;
            int left = 0;
            int right = 0;
            if (umap.find(nums[i] - 1) != umap.end())
                left = umap[nums[i] - 1];
            if (umap.find(nums[i] + 1) != umap.end())
                right = umap[nums[i] + 1];
            int sum = left + right + 1;
            max = std::max(max, sum);
            umap[nums[i]] = sum;
            umap[nums[i] - left] = sum;
            umap[nums[i] + right] = sum;
        }
        return max;
    }
};

Approach 3:

// HashSet and Intelligent Sequence Building.
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int n = nums.size();
        unordered_set<int> uset;
        for (int i = 0; i < n; ++i)
        {
            uset.insert(nums[i]);
        }
        int maxRes = 0;
        for (unordered_set<int>::iterator it = uset.begin(); it != uset.end(); ++it)
        {
            if (uset.find(*it - 1) == uset.end()) // This makes it O(n).
            {
                int curr = *it + 1;
                int count = 1;
                while (uset.find(curr) != uset.end())
                {
                    count++;
                    curr++;
                }
                maxRes = std::max(maxRes, count);
            }
        }
        return maxRes;
    }
};