Longest Consecutive Subsequence

Determine the length of the largest subsequence in an integer array where the components are consecutive integers; the numbers can be in any order.

Examples:  

Input: arr[] = {1, 9, 3, 10, 4, 20, 2}
Output: 4
Explanation: The subsequence 1, 3, 4, 2 is the longest subsequence of consecutive elements

Input: arr[] = {36, 41, 56, 35, 44, 33, 34, 92, 43, 32, 42}
Output: 5
Explanation: The subsequence 36, 35, 33, 34, 32 is the longest subsequence of consecutive elements.

[Naive Approach] Using Sorting – O(N*logN) Time and O(N) Space:

Finding the longest subarray with consecutive elements is the first step in sorting the array. Run a loop after sorting the array and eliminating entries that appear more than once, maintaining a count and max (both originally zero). Run a loop from beginning to end, setting the count to 1 if the current element is not equal to the previous (element+1); otherwise, increase the count. With a maximum of count and max, update max.

To solve the issue, take the actions listed below:

• Set the initial values for ans and countConsecutive to 0.
• Arr[] should be sorted.
• Navigate over the arr[ to store the distinct elements in the dist[] array.
• To determine the number of consecutive entries and preserve the answer variable, traverse the dist[] array.

C++

// C++ program to find longest
// contiguous subsequence
#include <bits/stdc++.h>
using namespace std;

// Returns length of the longest
// contiguous subsequence
int findLongestConseqSubseq(int arr[], int n)
{
    int ans = 0, count = 0;

    // sort the array
    sort(arr, arr + n);

    vector<int> v;
    v.push_back(arr[0]);

    // insert repeated elements only once in the vector
    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[i - 1])
            v.push_back(arr[i]);
    }
    // find the maximum length
    // by traversing the array
    for (int i = 0; i < v.size(); i++) {

        // Check if the current element is equal
        // to previous element +1
        if (i > 0 && v[i] == v[i - 1] + 1)
            count++;
        // reset the count
        else
            count = 1;

        // update the maximum
        ans = max(ans, count);
    }
    return ans;
}

// Driver code
int main()
{
    int arr[] = { 1, 2, 2, 3 };
    int n = sizeof arr / sizeof arr[0];
    cout << "Length of the Longest contiguous subsequence "
            "is "
         << findLongestConseqSubseq(arr, n);
    return 0;
}

Java

// Java program to find longest
// contiguous subsequence
import java.io.*;
import java.util.*;

class GFG {

    static int findLongestConseqSubseq(int arr[], int n)
    {

        // Sort the array
        Arrays.sort(arr);

        int ans = 0, count = 0;

        ArrayList<Integer> v = new ArrayList<Integer>();
        v.add(10);

        // Insert repeated elements
        // only once in the vector
        for (int i = 1; i < n; i++) {
            if (arr[i] != arr[i - 1])
                v.add(arr[i]);
        }

        // Find the maximum length
        // by traversing the array
        for (int i = 0; i < v.size(); i++) {

            // Check if the current element is
            // equal to previous element +1
            if (i > 0 && v.get(i) == v.get(i - 1) + 1)
                count++;
            else
                count = 1;

            // Update the maximum
            ans = Math.max(ans, count);
        }
        return ans;
    }

    // Driver code
    public static void main(String[] args)
    {
        int arr[] = { 1, 9, 3, 10, 4, 20, 2 };
        int n = arr.length;

        System.out.println(
            "Length of the Longest "
            + "contiguous subsequence is "
            + findLongestConseqSubseq(arr, n));
    }
}

Python

# Python3 program to find longest
# contiguous subsequence

# Returns length of the longest
# contiguous subsequence


def findLongestConseqSubseq(arr, n):

    ans = 0
    count = 0

    # Sort the array
    arr.sort()

    v = []

    v.append(arr[0])

    # Insert repeated elements only
    # once in the vector
    for i in range(1, n):
        if (arr[i] != arr[i - 1]):
            v.append(arr[i])

    # Find the maximum length
    # by traversing the array
    for i in range(len(v)):

        # Check if the current element is
        # equal to previous element +1
        if (i > 0 and v[i] == v[i - 1] + 1):
            count += 1

        # Reset the count
        else:
            count = 1

        # Update the maximum
        ans = max(ans, count)

    return ans


# Driver code
arr = [1, 2, 2, 3]
n = len(arr)

print("Length of the Longest contiguous subsequence is",
      findLongestConseqSubseq(arr, n))

JS

// JavaScript program to find longest
        // contiguous subsequence

        // Returns length of the longest
        // contiguous subsequence
        function findLongestConseqSubseq(arr, n) {
            let ans = 0, count = 0;

            // sort the array
            arr.sort(function (a, b) { return a - b; })

            var v = [];
            v.push(arr[0]);

            //insert repeated elements only once in the vector
            for (let i = 1; i < n; i++) {
                if (arr[i] != arr[i - 1])
                    v.push(arr[i]);
            }
            // find the maximum length
            // by traversing the array
            for (let i = 0; i < v.length; i++) {

                // Check if the current element is equal
                // to previous element +1
                if (i > 0 && v[i] == v[i - 1] + 1)
                    count++;
                // reset the count
                else
                    count = 1;

                // update the maximum
                ans = Math.max(ans, count);
            }
            return ans;
        }

        // Driver code

        let arr = [1, 2, 2, 3];
        let n = arr.length;
        console.log(
        "Length of the Longest contiguous subsequence is "
        +findLongestConseqSubseq(arr, n)
        );

Output

Length of the Longest contiguous subsequence is 3

Time complexity: O(Nlog(N)), Time to sort the array is O(Nlog(N)).
Auxiliary space: O(N). Extra space is needed for storing distinct elements.