Given an array of positive integers. Find the length of the longest sub-sequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in any order.

Example 1:

Input:

N = 7

*a[] = {2,6,1,9,4,5,3}*

Output:

6

Explanation:

The consecutive numbers here

are 1, 2, 3, 4, 5, 6. These 6

numbers form the longest consecutive

subsequence.

It is a MEDIUM LEVEL question, asked in **Amazon**,**Walmart**, **Microsoft**.

To solve this question click here:(https://practice.geeksforgeeks.org/problems/longest-consecutive-subsequence2449/1)

**Approach 1:**

It can be solved if we first sort the array and then find the longest subsequence. Write your code while keeping in mind that the elements can repeat.

This approach is not that efficient as the *Time Complexity is O(nlog n+n)* as to sorting algorithm will take time of nlogn.

**Approach 2:**

In second method I used **HashSet** to:

-remove duplicate elements from the array.

-to find the starting element of the sequence.

*Time Complexity: O(n)
Space Complexity: O(n)*

**JAVA CODE**

```
import java.util.*;
class LongestConsecutiveSeq{
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
System.out.println("Enter the size of the array:");
int n=sc.nextInt();
int[] arr=new int[n];
System.out.println("Enter the elements of the array:");
for(int i=0;i<n;i++)
{
arr[i]=sc.nextInt();
}
System.out.println(findLongestConseqSubseq(arr,n));
}
static int findLongestConseqSubseq(int arr[], int n)
{
//creating hashSet to remove duplicacy
HashSet<Integer> st=new HashSet<>();
for(int i=0;i<n;i++)
st.add(arr[i]);
int ans=0,c=1;
for(int i=0;i<n;i++)
{
c=1;
if(!st.contains(arr[i]-1))
{
int val=arr[i]+1;
while(st.contains(val))
{
val++;
c++;
}
ans=Math.max(ans,c);
}
}
return ans;
}
}
```

## Top comments (0)