Find the longest subsequence formed by consecutive integers

Posted in

Find the longest subsequence formed by consecutive integers
vinaykhatri

Vinay Khatri
Last updated on March 28, 2024

    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:

    Leave a Comment on this Post

    0 Comments