# Question

Formatted question description: https://leetcode.ca/all/128.html

128. Longest Consecutive Sequence

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

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

@tag-array



# Algorithm

For every num existed in set, try to probe to right to see if following numbers are also in set, and record longest possible sequence.

# Code

Java

• import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Longest_Consecutive_Sequence {

// Time complexity : O(n)
// Space complexity : O(n)
class Solution_oN {
public int longestConsecutive(int[] nums) {

Set<Integer> hs = new HashSet<Integer>();

// remove duplicates
for (int num : nums) {
}

int longestStreak = 0;

for (int num : hs) {
if (!hs.contains(num - 1)) {
int currentNum = num;
int currentStreak = 1;

while (hs.contains(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}

longestStreak = Math.max(longestStreak, currentStreak);
}
}

return longestStreak;
}
}

class Solution_sort {
public int longestConsecutive(int[] nums) {
if (nums.length == 0) {
return 0;
}

Arrays.sort(nums);

int longestStreak = 1;
int currentStreak = 1;

for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i-1]) {
if (nums[i] == nums[i-1]+1) {
currentStreak += 1;
}
else {
longestStreak = Math.max(longestStreak, currentStreak);
currentStreak = 1;
}
}
}

return Math.max(longestStreak, currentStreak);
}
}
}

• // OJ: https://leetcode.com/problems/longest-consecutive-sequence/
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/longest-consecutive-sequence/discuss/41088/Possibly-shortest-cpp-solution-only-6-lines.
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_map<int, int> m;
int ans = 0;
for (int n : nums) {
if (m[n]) continue;
ans = max(ans, m[n] = m[n - m[n - 1]] = m[n + m[n + 1]] = m[n - 1] + m[n + 1] + 1);
}
return ans;
}
};

• class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
s, res = set(nums), 0
for num in nums:
if num - 1 not in s:
t, next = 1, num + 1
while next in s:
t, next = t + 1, next + 1
res = max(res, t)
return res

############

class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
ans = 0
s = set(nums)
for num in nums:
if num in s:
cnt = 1
right = num + 1
left = num - 1
while left in s:
cnt += 1
left -= 1
while right in s: