Find the longest subsequence formed by consecutive integers

Problem

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

Sample Input

[1, 2, 3, 4, 55]

Sample Output

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:
        s.add(itr)
    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) {
            s.Add(arr[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:

• Python Program to Check Leap Year
• Count the number of strictly increasing subarrays in an array
• Python Program to Swap Two Variables
• Find equilibrium index of the array
• How to Find Square Root in Python?
• 4–Sum Problem | Quadruplets with a given sum
• WAP to print the truth table for XY+Z
• Print all triplets that form a geometric progression
• WAP to find the divisors of a positive Integer
• Longest Subarray with Contiguous Elements