# 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;
}
};