# Longest Consecutive Sequence in an Array

Problem Statement: You are given an array of ‘N’ integers. You need to find the length of the longest sequence which contains the consecutive elements.

Examples:

```Example 1:

Input: [100, 200, 1, 3, 2, 4]

Output: 4

Explanation: The longest consecutive subsequence is 1, 2, 3, and 4.

Input: [3, 8, 5, 7, 6]

Output: 4

Explanation: The longest consecutive subsequence is 5, 6, 7, and 8.```

# Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

## Solution 1: (Brute force)

Approach: We can simply sort the array and run a for loop to find the longest consecutive sequence.

Code:

## C++ Code

``````#include<bits/stdc++.h>
using namespace std;
int longestConsecutive(vector<int> nums) {
if(nums.size() == 0 ){
return 0;
}

sort(nums.begin(),nums.end());

int ans = 1;
int prev = nums;
int cur = 1;

for(int i = 1;i < nums.size();i++){
if(nums[i] == prev+1){
cur++;
}
else if(nums[i] != prev){
cur = 1;
}
prev = nums[i];
ans = max(ans, cur);
}
return ans;
}
int main()
{
vector<int> arr{100,200,1,2,3,4};
int lon=longestConsecutive(arr);
cout<<"The longest consecutive sequence is "<<lon<<endl;

}
``````

Output:

The longest consecutive sequence is 4

Time Complexity: We are first sorting the array which will take O(N * log(N)) time and then we are running a for loop which will take O(N) time. Hence, the overall time complexity will be O(N * log(N)).
Space Complexity: The space complexity for the above approach is O(1) because we are not using any auxiliary space

## Java Code

``````import java.util.*;
class TUF{
public static int longestConsecutive(int[] nums) {
if(nums.length == 0 || nums == null){
return 0;
}

Arrays.sort(nums);

int ans = 1;
int prev = nums;
int cur = 1;

for(int i = 1;i < nums.length;i++){
if(nums[i] == prev+1){
cur++;
}
else if(nums[i] != prev){
cur = 1;
}
prev = nums[i];
ans = Math.max(ans, cur);
}
return ans;
}
public static void main(String args[])
{
int arr[]={100,200,1,2,3,4};
int lon=longestConsecutive(arr);
System.out.println("The longest consecutive sequence is "+lon);

}
}``````

Output:

The longest consecutive sequence is 4

Time Complexity: We are first sorting the array which will take O(N * log(N)) time and then we are running a for loop which will take O(N) time. Hence, the overall time complexity will be O(N * log(N)).
Space Complexity: The space complexity for the above approach is O(1) because we are not using any auxiliary space

## Solution 2: (Optimal Approach)

Approach: We will first push all are elements in the HashSet. Then we will run a for loop and check for any number(x) if it is the starting number of the consecutive sequence by checking if the HashSet contains (x-1) or not. If ‘x’ is the starting number of the consecutive sequence we will keep searching for the numbers y = x+1, x+2, x+3, ….. And stop at the first ‘y’ which is not present in the HashSet. Using this we can calculate the length of the longest consecutive subsequence.

Code:

## C++ Code

``````#include<bits/stdc++.h>

using namespace std;
int longestConsecutive(vector < int > & nums) {
set < int > hashSet;
for (int num: nums) {
hashSet.insert(num);
}

int longestStreak = 0;

for (int num: nums) {
if (!hashSet.count(num - 1)) {
int currentNum = num;
int currentStreak = 1;

while (hashSet.count(currentNum + 1)) {
currentNum += 1;
currentStreak += 1;
}

longestStreak = max(longestStreak, currentStreak);
}
}

return longestStreak;
}
int main() {
vector<int> arr{100,200,1,2,3,4};
int lon = longestConsecutive(arr);
cout << "The longest consecutive sequence is " << lon << endl;

}``````

Output:

The longest consecutive sequence is 4

Time Complexity: The time complexity of the above approach is O(N) because we traverse each consecutive subsequence only once. (assuming hashset takes O(1) to search)
Space Complexity: The space complexity of the above approach is O(N) because we are maintaining a HashSet.

## Java Code

``````import java.util.*;
class TUF {
public static int longestConsecutive(int[] nums) {
Set < Integer > hashSet = new HashSet < Integer > ();
for (int num: nums) {
}

int longestStreak = 0;

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

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

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

return longestStreak;
}
public static void main(String args[]) {
int arr[]={100,200,1,2,3,4};
int lon = longestConsecutive(arr);
System.out.println("The longest consecutive sequence is " + lon);

}
}``````

Output:

The longest consecutive sequence is 4

Time Complexity: The time complexity of the above approach is O(N) because we traverse each consecutive subsequence only once. (assuming hashset takes O(1) to search)
Space Complexity: The space complexity of the above approach is O(N) because we are maintaining a HashSet.

Special thanks to Nishant Rana for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article