.png)
Longest Consecutive Sequence
Problem Statement
You are given an unsorted array of integers.
Your task is to find the length of the longest consecutive elements sequence.
A consecutive sequence means numbers appearing in increasing order with a difference of 1,
and the sequence does not need to be contiguous in the array.
Example 1
Input
arr = [100, 4, 200, 1, 3, 2]
Output
4
Explanation
Longest consecutive sequence is [1, 2, 3, 4]
Example 2
Input
arr = [0, 3, 7, 2, 5, 8, 4, 6, 0, 1]
Output
9
Why This Problem Is Important
- Very frequently asked interview problem
- Tests hashing and sequence logic
- Requires optimization beyond sorting
- Foundation for set-based searching problems
- Appears in FAANG interviews
Approaches Overview
| Approach | Technique | Time | Space |
|---|---|---|---|
| Approach 1 | Brute Force | O(n²) | O(1) |
| Approach 2 | Sorting | O(n log n) | O(1) |
| Approach 3 | Hash Set (Optimal) | O(n) | O(n) |
Approach 1: Brute Force
Idea
For every element, check whether the next consecutive number exists in the array and keep extending the sequence.
Algorithm
- For each element arr[i]
- Start with current = arr[i]
- Check if current + 1 exists in array
- Keep counting until the sequence breaks
- Track maximum length
Time & Space Complexity
- Time: O(n²)
- Space: O(1)
Implementations
C
#include
int exists(int arr[], int n, int x) {
for(int i = 0; i < n; i++)
if(arr[i] == x) return 1;
return 0;
}
int main() {
int arr[] = {100,4,200,1,3,2};
int n = 6, maxLen = 0;
for(int i = 0; i < n; i++) {
int curr = arr[i], count = 1;
while(exists(arr, n, curr + 1)) {
curr++;
count++;
}
if(count > maxLen) maxLen = count;
}
printf("%d", maxLen);
return 0;
}
C++
#include
using namespace std;
bool exists(int arr[], int n, int x) {
for(int i = 0; i < n; i++)
if(arr[i] == x) return true;
return false;
}
int main() {
int arr[] = {100,4,200,1,3,2};
int n = 6, maxLen = 0;
for(int i = 0; i < n; i++) {
int curr = arr[i], count = 1;
while(exists(arr, n, curr + 1)) {
curr++;
count++;
}
maxLen = max(maxLen, count);
}
cout << maxLen;
return 0;
}
Java
public class LongestConsecutive {
static boolean exists(int[] arr, int x) {
for(int num : arr)
if(num == x) return true;
return false;
}
public static void main(String[] args) {
int[] arr = {100,4,200,1,3,2};
int maxLen = 0;
for(int num : arr) {
int curr = num, count = 1;
while(exists(arr, curr + 1)) {
curr++;
count++;
}
maxLen = Math.max(maxLen, count);
}
System.out.print(maxLen);
}
}
Python
arr = [100,4,200,1,3,2]
maxLen = 0
for num in arr:
curr = num
count = 1
while curr + 1 in arr:
curr += 1
count += 1
maxLen = max(maxLen, count)
print(maxLen)
JavaScript
let arr = [100,4,200,1,3,2];
let maxLen = 0;
for (let num of arr) {
let curr = num, count = 1;
while (arr.includes(curr + 1)) {
curr++;
count++;
}
maxLen = Math.max(maxLen, count);
}
console.log(maxLen);
_1770813811.png)
Approach 2: Sorting
Idea
Sort the array and count consecutive numbers while skipping duplicates.
Algorithm
- Sort the array
- Initialize count = 1, maxLen = 1
- Traverse array
- If arr[i] == arr[i-1] + 1, increment count
- If duplicate, skip
- Else reset count
- Update max length
Time & Space Complexity
- Time: O(n log n)
- Space: O(1)
Implementations
C++
#include
#include
using namespace std;
int main() {
int arr[] = {100,4,200,1,3,2};
int n = 6;
sort(arr, arr + n);
int maxLen = 1, count = 1;
for(int i = 1; i < n; i++) {
if(arr[i] == arr[i-1] + 1)
count++;
else if(arr[i] != arr[i-1])
count = 1;
maxLen = max(maxLen, count);
}
cout << maxLen;
return 0;
}
Java
import java.util.Arrays;
public class LongestConsecutive {
public static void main(String[] args) {
int[] arr = {100,4,200,1,3,2};
Arrays.sort(arr);
int maxLen = 1, count = 1;
for(int i = 1; i < arr.length; i++) {
if(arr[i] == arr[i-1] + 1)
count++;
else if(arr[i] != arr[i-1])
count = 1;
maxLen = Math.max(maxLen, count);
}
System.out.print(maxLen);
}
}
Python
arr = [100,4,200,1,3,2]
arr.sort()
maxLen = count = 1
for i in range(1, len(arr)):
if arr[i] == arr[i-1] + 1:
count += 1
elif arr[i] != arr[i-1]:
count = 1
maxLen = max(maxLen, count)
print(maxLen)
JavaScript
let arr = [100,4,200,1,3,2];
arr.sort((a,b) => a - b);
let maxLen = 1, count = 1;
for (let i = 1; i < arr.length; i++) {
if (arr[i] === arr[i-1] + 1)
count++;
else if (arr[i] !== arr[i-1])
count = 1;
maxLen = Math.max(maxLen, count);
}
console.log(maxLen);
Approach 3: Hash Set (Optimal)
Idea
Use a hash set to allow O(1) lookup.
Start counting only when the number is the start of a sequence.
Algorithm
- Insert all elements into a hash set
- For each element
- If num - 1 does NOT exist → start a sequence
- Keep checking num + 1, num + 2...
- Track maximum length
Time & Space Complexity
- Time: O(n)
- Space: O(n)
Implementations
C++
#include
#include
using namespace std;
int main() {
int arr[] = {100,4,200,1,3,2};
int n = 6;
unordered_set s(arr, arr + n);
int maxLen = 0;
for(int num : s) {
if(s.find(num - 1) == s.end()) {
int curr = num, count = 1;
while(s.find(curr + 1) != s.end()) {
curr++;
count++;
}
maxLen = max(maxLen, count);
}
}
cout << maxLen;
return 0;
}
Java
import java.util.HashSet;
public class LongestConsecutive {
public static void main(String[] args) {
int[] arr = {100,4,200,1,3,2};
HashSet set = new HashSet<>();
for(int num : arr)
set.add(num);
int maxLen = 0;
for(int num : set) {
if(!set.contains(num - 1)) {
int curr = num, count = 1;
while(set.contains(curr + 1)) {
curr++;
count++;
}
maxLen = Math.max(maxLen, count);
}
}
System.out.print(maxLen);
}
}
Python
arr = [100,4,200,1,3,2]
s = set(arr)
maxLen = 0
for num in s:
if num - 1 not in s:
curr = num
count = 1
while curr + 1 in s:
curr += 1
count += 1
maxLen = max(maxLen, count)
print(maxLen)
JavaScript
let arr = [100,4,200,1,3,2];
let set = new Set(arr);
let maxLen = 0;
for (let num of set) {
if (!set.has(num - 1)) {
let curr = num, count = 1;
while (set.has(curr + 1)) {
curr++;
count++;
}
maxLen = Math.max(maxLen, count);
}
}
console.log(maxLen);
Dry Run (Hash Set Approach)
Input
[100, 4, 200, 1, 3, 2]
- Start at 1 → sequence 1,2,3,4 → length = 4
- Other numbers are skipped as they are not sequence starts
Final Answer
4
Summary
- Brute force is inefficient
- Sorting improves logic but costs time
- Hash Set approach is optimal and interview-preferred
- Solves the problem in linear time
Next Problem in the Series
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
