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
Constraints:
0 <= nums.length <= 105-109 <= nums[i] <= 109
Solutions#
Solution 1: Sorting#
First, we sort the array, then use a variable $t$ to record the current length of the consecutive sequence, and a variable $ans$ to record the length of the longest consecutive sequence.
Next, we start traversing the array from index $i=1$. For the current element $nums[i]$:
- If $nums[i] = nums[i-1]$, it means the current element is repeated and does not need to be considered.
- If $nums[i] = nums[i-1] + 1$, it means the current element can be appended to the previous consecutive sequence to form a longer consecutive sequence. We update $t = t + 1$, and then update the answer $ans = \max(ans, t)$.
- Otherwise, it means the current element cannot be appended to the previous consecutive sequence, and we reset $t$ to $1$.
Finally, we return the answer $ans$.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Here, $n$ is the length of the array.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
n = len(nums)
if n < 2:
return n
nums.sort()
ans = t = 1
for a, b in pairwise(nums):
if a == b:
continue
if a + 1 == b:
t += 1
ans = max(ans, t)
else:
t = 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public int longestConsecutive(int[] nums) {
int n = nums.length;
if (n < 2) {
return n;
}
Arrays.sort(nums);
int ans = 1, t = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] == nums[i - 1]) {
continue;
}
if (nums[i] == nums[i - 1] + 1) {
ans = Math.max(ans, ++t);
} else {
t = 1;
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int n = nums.size();
if (n < 2) {
return n;
}
sort(nums.begin(), nums.end());
int ans = 1, t = 1;
for (int i = 1; i < n; ++i) {
if (nums[i] == nums[i - 1]) {
continue;
}
if (nums[i] == nums[i - 1] + 1) {
ans = max(ans, ++t);
} else {
t = 1;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func longestConsecutive(nums []int) int {
n := len(nums)
if n < 2 {
return n
}
sort.Ints(nums)
ans, t := 1, 1
for i, x := range nums[1:] {
if x == nums[i] {
continue
}
if x == nums[i]+1 {
t++
ans = max(ans, t)
} else {
t = 1
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| function longestConsecutive(nums: number[]): number {
const n = nums.length;
if (n < 2) {
return n;
}
let ans = 1;
let t = 1;
nums.sort((a, b) => a - b);
for (let i = 1; i < n; ++i) {
if (nums[i] === nums[i - 1]) {
continue;
}
if (nums[i] === nums[i - 1] + 1) {
ans = Math.max(ans, ++t);
} else {
t = 1;
}
}
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| use std::collections::HashSet;
impl Solution {
#[allow(dead_code)]
pub fn longest_consecutive(nums: Vec<i32>) -> i32 {
let mut s = HashSet::new();
let mut ret = 0;
// Initialize the set
for num in &nums {
s.insert(*num);
}
for num in &nums {
if s.contains(&(*num - 1)) {
continue;
}
let mut cur_num = num.clone();
while s.contains(&cur_num) {
cur_num += 1;
}
// Update the answer
ret = std::cmp::max(ret, cur_num - num);
}
ret
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| /**
* @param {number[]} nums
* @return {number}
*/
var longestConsecutive = function (nums) {
const n = nums.length;
if (n < 2) {
return n;
}
nums.sort((a, b) => a - b);
let ans = 1;
let t = 1;
for (let i = 1; i < n; ++i) {
if (nums[i] === nums[i - 1]) {
continue;
}
if (nums[i] === nums[i - 1] + 1) {
ans = Math.max(ans, ++t);
} else {
t = 1;
}
}
return ans;
};
|
Solution 2: Hash Table#
We use a hash table to store all elements in the array, and then traverse each element $x$ in the array. If the predecessor $x-1$ of the current element is not in the hash table, then we start with the current element and continuously try to match $x+1, x+2, x+3, \dots$, until no match is found. The length of the match at this time is the longest consecutive sequence length starting with $x$, and we update the answer accordingly.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array.
1
2
3
4
5
6
7
8
9
10
11
| class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
s = set(nums)
ans = 0
for x in nums:
if x - 1 not in s:
y = x + 1
while y in s:
y += 1
ans = max(ans, y - x)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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 : nums) {
if (!s.contains(x - 1)) {
int y = x + 1;
while (s.contains(y)) {
++y;
}
ans = Math.max(ans, y - x);
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> s(nums.begin(), nums.end());
int ans = 0;
for (int x : nums) {
if (!s.count(x - 1)) {
int y = x + 1;
while (s.count(y)) {
y++;
}
ans = max(ans, y - x);
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func longestConsecutive(nums []int) (ans int) {
s := map[int]bool{}
for _, x := range nums {
s[x] = true
}
for _, x := range nums {
if !s[x-1] {
y := x + 1
for s[y] {
y++
}
ans = max(ans, y-x)
}
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function longestConsecutive(nums: number[]): number {
const s: Set<number> = new Set(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;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| /**
* @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;
};
|
