Algorithm
Problem Name: 128. Longest Consecutive Sequence
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
Example 1:
Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9
Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct e_s {
int key;
int len;
struct e_s *shadow;
} e_t;
#define HSZ 1000
void put(e_t **htable, int key, int len) {
e_t *e = malloc(sizeof(e_t));
//assert(e);
e->key = key;
e->len = len;
e->shadow = htable[key % HSZ];
htable[key % HSZ] = e;
}
int lookup(e_t **htable, int key, int **lp) {
e_t *e = htable[key % HSZ];
// Runtime Error Message:
// Line 20: member access within misaligned address 0x000001ea62f4 for type 'struct e_t',
// which requires 8 byte alignment
while (e && e->key != key) {
e = e->shadow;
}
if (e) {
*lp = &e->len;
return e->len;
}
return 0;
}
int longestConsecutive(int* nums, int numsSize) {
int i, l, r, x, len = 0;
e_t *htable[HSZ] = { 0 };
int *llp, *rlp;
// make a hash table to store the length of consecutive of current number
// and update the length of consecutive of left and right boundary
for (i = 0; i < numsSize; i ++) {
if (lookup(htable, nums[i], &llp) == 0) {
l = lookup(htable, nums[i] - 1, &llp);
r = lookup(htable, nums[i] + 1, &rlp);
x = l + r + 1;
put(htable, nums[i], x);
if (l) *llp = x;
if (r) *rlp = x;
if (len < x) len = x;
}
}
// TODO: clean up memory
return len;
}
Input
Input: nums = [100,4,200,1,3,2]
Output
4
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int maxlen = 0;
unordered_map < int, int>m;
for(auto x: nums){
if(m[x]) continue;
int left = m[x - 1];
int right = m[x + 1];
m[x + right] = m[x - left] = m[x] = left + right + 1;
maxlen = max(maxlen, m[x]);
}
return maxlen;
}
};
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map < int, int>m;
int res = 0;
for (int& x: nums) {
if (m[x]) {
continue;
}
int l = m[x - 1];
int r = m[x + 1];
m[x] = l + r + 1;
m[x - l] = l + r + 1;
m[x + r] = l + r + 1;
res = max(res, m[x]);
}
return res;
}
};
Input
Input: nums = [100,4,200,1,3,2]
Output
4
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int longestConsecutive(int[] nums) {
Set set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int maxLength = 0;
for (int num : set) {
if (!set.contains(num - 1)) {
int currNum = num;
int currentLength = 1;
while (set.contains(currNum + 1)) {
currNum++;
currentLength++;
}
maxLength = Math.max(currentLength, maxLength);
}
}
return maxLength;
}
}
Input
nums = [0,3,7,2,5,8,4,6,0,1]
Output
9
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const longestConsecutive = function(nums) {
if(nums.length === 0) return 0
nums.sort((a, b) => a - b)
let max = 1
let cur = 1
for(let i = 1; i < nums.length; i++) {
if(nums[i] - nums[i-1] === 1) {
cur += 1
max = Math.max(max, cur)
} else if(nums[i] - nums[i-1] === 0> {
} else {
cur = 1
}
}
return max
};
Input
nums = [0,3,7,2,5,8,4,6,0,1]
Output
9
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def longestConsecutive(self, nums):
res, items = 0, set(nums)
for num in items:
if num - 1 not in items:
cur = 1
while num + 1 in items:
num, cur = num + 1, cur + 1
if cur > res: res = cur
return res
Input
nums = [100,4,200,1,3,2]
Output
4
#6 Code Example with C# Programming
Code -
C# Programming
using System;
using System.Collections.Generic;
namespace LeetCode
{
public class _0128_LongestConsecutiveSequence
{
public int LongestConsecutive(int[] nums)
{
var hashSet = new HashSet < int>(nums);
var longestStreak = 0;
for (int i = 0; i < nums.Length; i++)
if (!hashSet.Contains(nums[i] - 1))
{
int currentNum = nums[i], currentStreak = 1;
while (hashSet.Contains(currentNum + 1))
{
currentNum += 1;
currentStreak++;
}
longestStreak = Math.Max(longestStreak, currentStreak);
}
return longestStreak;
}
}
}
Input
nums = [100,4,200,1,3,2]
Output
4