**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:4Explanation:The longest consecutive subsequence is 1, 2, 3, and 4.Input:[3, 8, 5, 7, 6]Output:4Explanation: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[0];
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[0];
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

## Python Code

```
from typing import List
def longestConsecutive(nums: List[int]) -> int:
if not nums:
return 0
nums.sort()
ans = 1
prev = nums[0]
cur = 1
for i in range(1, len(nums)):
if nums[i] == prev + 1:
cur += 1
elif nums[i] != prev:
cur = 1
prev = nums[i]
ans = max(ans, cur)
return ans
if __name__ == "__main__":
arr = [100, 200, 1, 2, 3, 4]
lon = longestConsecutive(arr)
print("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 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) {
hashSet.add(num);
}
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.

## Python Code

```
from typing import List
def longestConsecutive(nums: List[int]) -> int:
hashSet = set()
for num in nums:
hashSet.add(num)
longestStreak = 0
for num in nums:
if (num - 1) not in hashSet:
currentNum = num
currentStreak = 1
while (currentNum + 1) in hashSet:
currentNum += 1
currentStreak += 1
longestStreak = max(longestStreak, currentStreak)
return longestStreak
if __name__ == "__main__":
arr = [100, 200, 1, 2, 3, 4]
lon = longestConsecutive(arr)
print("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 and Sudip Ghosh for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, *please check out this article