## 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;
} 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;
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) {
}
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;
}
``````
Copy The Code &

Input

cmd
Input: nums = [100,4,200,1,3,2]

Output

cmd
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;
}
};
``````
Copy The Code &

Input

cmd
Input: nums = [100,4,200,1,3,2]

Output

cmd
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) {
}
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;
}
}
``````
Copy The Code &

Input

cmd
nums = [0,3,7,2,5,8,4,6,0,1]

Output

cmd
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
};
``````
Copy The Code &

Input

cmd
nums = [0,3,7,2,5,8,4,6,0,1]

Output

cmd
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
``````
Copy The Code &

Input

cmd
nums = [100,4,200,1,3,2]

Output

cmd
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;
}
}
}
``````
Copy The Code &

Input

cmd
nums = [100,4,200,1,3,2]

Output

cmd
4