Practice › Arrays
Longest Consecutive Sequence
Medium · Arrays · Asked at Google, Amazon, Microsoft, Uber
Print the length of the longest sequence of consecutive integers that can be formed from the array values (order in the array does not matter).
Input
First line: n. Second line: n space-separated integers.
Output
The length of the longest consecutive sequence.
Constraints
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a[i] ≤ 10^9
Put everything in a hash set and only start counting from numbers whose predecessor is missing — O(n).
Example 1
Input
6 100 4 200 1 3 2
Output
4
Example 2
Input
10 0 3 7 2 5 8 4 6 0 1
Output
9
Hints
- Sorting gives O(n log n). A hash set can do it in O(n).
- Only start counting from x when x − 1 is not in the set — then x begins a sequence.
Approach
Put every value in a hash set (duplicates disappear). For each x whose predecessor x − 1 is missing, count upward x, x+1, x+2… while they are in the set. Each number is visited by at most one such count, so the total work is O(n). (Sorting and scanning is a simpler O(n log n) alternative.)
Complexity: O(n) average time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
unordered_set<long long> s;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
s.insert(x);
}
int best = 0;
for (long long x : s) {
if (s.count(x - 1)) continue;
int len = 1;
while (s.count(x + len)) len++;
best = max(best, len);
}
cout << best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
s = set(data[1 : data[0] + 1])
best = 0
for x in s:
if x - 1 in s:
continue
length = 1
while x + length in s:
length += 1
best = max(best, length)
print(best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Set<Long> s = new HashSet<>();
for (int i = 0; i < n; i++) s.add(sc.nextLong());
int best = 0;
for (long x : s) {
if (s.contains(x - 1)) continue;
int len = 1;
while (s.contains(x + len)) len++;
best = Math.max(best, len);
}
System.out.println(best);
}
}Solve Longest Consecutive Sequence online · All practice problems