# Find the longest subsequence formed by consecutive integers

Posted in

Vinay Khatri
Last updated on August 10, 2024

## Problem

Given an array of integers, find the longest subsequence of consecutive integers.

#### Sample Input

`[1, 2, 3, 4, 55]`

`4`

#### Explanation

`The subsequence is [1, 2, 3, 4]`

### Approach

We can insert all the elements in a set. We then look for the starting element of a subsequence. To check this, suppose the current element is ``` arr[i] ``` , then if ``` arr[i] ``` ``` -1 ``` is not found in this set, then this is the starting element of the subsequence. We can then iterate until ``` arr[i]+1 ``` exists in the set and update the answer. This approach takes O(N) time and O(N) space.

### C++ Programming

```#include <bits/stdc++.h>
using namespace std;

int solve(int arr[], int n)
{
unordered_set<int> s;
int ans = 0;

for (int i = 0; i < n; i++)
s.insert(arr[i]);

for (int i = 0; i < n; i++)
{

if (s.find(arr[i] - 1) == s.end())
{

int j = arr[i];
while (s.find(j) != s.end())
j++;

ans = max(ans, j - arr[i]);
}
}
return ans;
}

int main()
{
int arr[] = { 1, 2, 3, 4, 55 };
int n = sizeof arr / sizeof arr[0];
cout << "Length of subsequence is " << solve(arr, n);
return 0;
}
```

Output

`Length of subsequence is 4`

### Python Programming

```def solve(arr, n):
s = set()
ans = 0
for itr in arr:
for i in range(n):
if (arr[i]-1) not in s:
j = arr[i]
while(j in s):
j += 1
ans = max(ans, j-arr[i])
return ans

arr = [1, 2, 3, 4, 55]
n = len(arr)
print("Length of subsequence is ", end=" ")
print(solve(arr, n))```

#### Output

`Length of subsequence is 4`

### C# Programming

```using System;
using System.Collections.Generic;

public class Solutions {

public static int solve(int[] arr, int n)
{
HashSet<int> s = new HashSet<int>();
int ans = 0;

for (int i = 0; i < n; ++i) {
}

for (int i = 0; i < n; ++i)
{

if (!s.Contains(arr[i] - 1))
{

int j = arr[i];
while (s.Contains(j))
{
j++;
}

if (ans < j - arr[i])
{
ans = j - arr[i];
}
}
}
return ans;
}

public static void Main(string[] args)
{
int[] arr = new int[] { 1, 2, 3, 4, 55 };
int n = arr.Length;
Console.WriteLine(
"Length of subsequence is "
+ solve(arr, n));
}
}```

#### Output

```Length of subsequence is 4
```

People are also reading: