Description
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
Example 3:
Input: nums = [1,0,1,2]
Output: 3
Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109
Solutions
Solution 1: Hash Table
We can use a hash table s to store all the elements in the array, a variable ans to record the length of the longest consecutive sequence, and a hash table d to record the length of the consecutive sequence each element x belongs to.
Next, we iterate through each element x in the array, using a temporary variable y to record the maximum value of the current consecutive sequence, initially y = x. Then, we continuously try to match y+1, y+2, y+3, \dots until we can no longer match. During this process, we remove the matched elements from the hash table s. The length of the consecutive sequence that the current element x belongs to is d[x] = d[y] + y - x, and then we update the answer ans = max(ans, d[x]).
After the iteration, we return the answer ans.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
PythonJavaC++GoTypeScriptRustJavaScript
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
s = set(nums)
ans = 0
d = defaultdict(int)
for x in nums:
y = x
while y in s:
s.remove(y)
y += 1
d[x] = d[y] + y - x
ans = max(ans, d[x])
return ans(code-box)
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> s = new HashSet<>();
for (int x : nums) {
s.add(x);
}
int ans = 0;
Map<Integer, Integer> d = new HashMap<>();
for (int x : nums) {
int y = x;
while (s.contains(y)) {
s.remove(y++);
}
d.put(x, d.getOrDefault(y, 0) + y - x);
ans = Math.max(ans, d.get(x));
}
return ans;
}
}(code-box)
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int ans = 0;
unordered_map<int, int> d;
for (int x : nums) {
int y = x;
while (s.contains(y)) {
s.erase(y++);
}
d[x] = (d.contains(y) ? d[y] : 0) + y - x;
ans = max(ans, d[x]);
}
return ans;
}
};(code-box)
func longestConsecutive(nums []int) (ans int) {
s := map[int]bool{}
for _, x := range nums {
s[x] = true
}
d := map[int]int{}
for _, x := range nums {
y := x
for s[y] {
delete(s, y)
y++
}
d[x] = d[y] + y - x
ans = max(ans, d[x])
}
return
}(code-box)
function longestConsecutive(nums: number[]): number {
const s = new Set(nums);
let ans = 0;
const d = new Map<number, number>();
for (const x of nums) {
let y = x;
while (s.has(y)) {
s.delete(y++);
}
d.set(x, (d.get(y) || 0) + (y - x));
ans = Math.max(ans, d.get(x)!);
}
return ans;
}(code-box)
use std::collections::{HashMap, HashSet};
impl Solution {
pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
let mut s: HashSet<i32> = nums.iter().cloned().collect();
let mut ans = 0;
let mut d: HashMap<i32, i32> = HashMap::new();
for &x in &nums {
let mut y = x;
while s.contains(&y) {
s.remove(&y);
y += 1;
}
let length = d.get(&(y)).unwrap_or(&0) + y - x;
d.insert(x, length);
ans = ans.max(length);
}
ans
}
}(code-box)
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
const s = new Set(nums);
let ans = 0;
const d = new Map();
for (const x of nums) {
let y = x;
while (s.has(y)) {
s.delete(y++);
}
d.set(x, (d.get(y) || 0) + (y - x));
ans = Math.max(ans, d.get(x));
}
return ans;
};(code-box)
Solution 2: Hash Table (Optimization)
Similar to Solution 1, we use a hash table s to store all the elements in the array and a variable ans to record the length of the longest consecutive sequence. However, we no longer use a hash table d to record the length of the consecutive sequence each element x belongs to. During the iteration, we skip elements where x-1 is also in the hash table s. If x-1 is in the hash table s, then x is definitely not the start of a consecutive sequence, so we can directly skip x.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
PythonJavaC++GoTypeScriptRustJavaScript
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
s = set(nums)
ans = 0
for x in s:
if x - 1 not in s:
y = x + 1
while y in s:
y += 1
ans = max(ans, y - x)
return ans(code-box)
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> s = new HashSet<>();
for (int x : nums) {
s.add(x);
}
int ans = 0;
for (int x : s) {
if (!s.contains(x - 1)) {
int y = x + 1;
while (s.contains(y)) {
++y;
}
ans = Math.max(ans, y - x);
}
}
return ans;
}
}(code-box)
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int ans = 0;
for (int x : s) {
if (!s.contains(x - 1)) {
int y = x + 1;
while (s.contains(y)) {
y++;
}
ans = max(ans, y - x);
}
}
return ans;
}
};(code-box)
func longestConsecutive(nums []int) (ans int) {
s := map[int]bool{}
for _, x := range nums {
s[x] = true
}
for x, _ := range s {
if !s[x-1] {
y := x + 1
for s[y] {
y++
}
ans = max(ans, y-x)
}
}
return
}(code-box)
function longestConsecutive(nums: number[]): number {
const s = new Set<number>(nums);
let ans = 0;
for (const x of s) {
if (!s.has(x - 1)) {
let y = x + 1;
while (s.has(y)) {
y++;
}
ans = Math.max(ans, y - x);
}
}
return ans;
}(code-box)
use std::collections::HashSet;
impl Solution {
pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
let s: HashSet<i32> = nums.iter().cloned().collect();
let mut ans = 0;
for &x in &s {
if !s.contains(&(x - 1)) {
let mut y = x + 1;
while s.contains(&y) {
y += 1;
}
ans = ans.max(y - x);
}
}
ans
}
}(code-box)
/**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
const s = new Set(nums);
let ans = 0;
for (const x of nums) {
if (!s.has(x - 1)) {
let y = x + 1;
while (s.has(y)) {
y++;
}
ans = Math.max(ans, y - x);
}
}
return ans;
};(code-box)
