Longest Consecutive Subsequence

Longest Consecutive Subsequence
Longest Consecutive Subsequence

Introduction

In this blog, you learn to solve the problem Longest Consecutive Subsequence. But before that, you need to be very clear about the definition of subsequence. Most of the people remain confused between subarray and subsequence, so let’s discuss them first.

Subarray is a continuous set of elements of an array, while the subsequence can contain array elements in any order. Subsequence doesn’t demand elements in a continuous manner. Let’s make it more evident with the help of the example below:

Suppose we are having an array arr = [1, 3, 5, 9, 10, 8, 6, 7].Now the subarray will be like [1,3,5] or [10, 8, 6] but the subsequence can include [1, 10, 7] or [5, 7].

The problem statement in your interviews for this problem will be stated like this:

Given an array of integers, print longest subsequence such that elements of the subsequence are consecutive integers, although they can be in any order.

Let’s see some examples to understand the problem better:

Suppose we are having an array of integers given below:

193104202

Now you have to give the longest consecutive subsequence as output that will be [1, 3, 4, 2]. I hope you got the problem statement clearly, so let’s move towards solving it.

Brute Force Solution Of Longest Consecutive Subsequence 

Let’s see the brute force, i.e., the easiest method for getting the longest consecutive subsequence.

Step 1. You need to sort the array in ascending order.

blog banner 1

Step 2. Compare the consecutive elements to get a maximum length subarray having consecutive integers as our output.

C++ Solution

#include <iostream>
using namespace std;

int lenOfSub(vector<int> &arr, int n) {

    // Sorting the given array 
    sort(arr.begin(), arr.end());

    //storing the length of the longest subsequence in it.
    int mx = 0;

    int count = 0;

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

        // Check if the previous value is consecutive to the current value.
        if (i > 0 && (arr[i] == arr[i - 1] + 1)) {
            count++;
        }

        // Skip if the current value is equal to the previous value.
        else if (i > 0 && arr[i] == arr[i - 1]) {
            continue;
        }
        // Resetting count for next consecutive subsequence.
        else {
            count = 1;
        }

        mx = max(mx, count);
        
    }

    return mx;
}

int main()
{
    vector<int> input = { 33, 20, 34, 30, 35};
    int n = 5;
 
    cout << "The length of the maximum consecutive subsequence is "
      <<lenOfSub(input, n);
 
    return 0;
}
Output: 
The length of the maximum consecutive subsequence is 3

Java Solution

import java.util.Arrays;

public class Solution {
    public static int lenSub(int[] arr, int N) {

        // Sorting the given array.
        Arrays.sort(arr);

        // Storing length of longest consecutive sequence.
        int mx = 0;
        int count = 0;

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

            // Check if the previous value is consecutive to the current value.
            if (i > 0 && (arr[i] == arr[i - 1] + 1)) {
                count++;

            }
            // Skip if the current value is equal to the previous value.
            else if (i > 0 && arr[i] == arr[i - 1]) {
                continue;
            }
            // Resetting count for next upcoming consecutive sequence.
            else {
                count = 1;
            }

            mx = Math.max(mx, count);
            
        }

        return mx;
    }
}

public static void main(String[] args)
    {
        int arr[] = {  2, 0, 6, 1, 5, 3, 7};
        int n = arr.length;
 
        System.out.println(
            "Length of the Longest "
            + "contiguous subsequence is "
            + lenSub(arr, n));
    }
}
Output: 
Length of the longest continuous subsequence is 4.

Time complexity: O(N*log(N))

Space Complexity: O(1)

This approach is relatively easy to implement. Isn’t it? Now try optimizing this solution here.

Optimized Approach Using Hashing

Hashing implies you can solve this problem using a set or map to decrease the time complexity. Let’s see the steps:- 

Step 1. You need to Store all the elements of the array in a set.

Step 2. Now, for every element in the set, you have to check whether it can be the starting element of the longest consecutive subsequence or not.To do so, for every arr[i] in set check if arr[i]-1 is present.If no, then it will be the starting element of the longest consecutive subsequence.

Step 3. Now iterate in the set to find all those numbers which are consecutive to arr[i] and store the count.

Step 4. Update the value of the answer if this count is greater than the previous one.

Let’s understand it better using code.

C++ Solution

#include <iostream>
#include <unordered_set>
using namespace std;

int lenSubsq(vector<int> &arr, int n) {
    // Storing length of longest consecutive sequence.
    int ans = 0;

    // Storing the length of the current consecutive Sequence.
    int count = 0;

    // Storing all the unique elements of an array.
    unordered_set<int> set;

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

    for (int i = 0; i < n; i++) {
        int prevElem = arr[i] - 1;

        if (set.find(prevElem) == set.end()) {
            int j = arr[i];
            
            while (set.find(j) != set.end()) {
                // The next consecutive element will be j + 1.
                j++;
            }

            // Update maximum length of consecutive sequence.
            ans = max(ans, j - arr[i]);
        }

    }

    return ans;
}

int main()
{
    vector<int> input = { 33, 20, 34, 30, 35};
    int n = 5;
 
    cout << "Length of maximum consecutive subsequence will be "
      <<lenSubsq(input, n);
 
    return 0;
}
Output: 
Length of maximum consecutive subsequence will be 3.

Java Solution

import java.util.HashSet;

public class Solution {
    public static int lenSubsq(int[] arr, int N) {
        // Storing length of longest consecutive sequence.
        int ans = 0;

        // Storing length of current consecutive Sequence.
        int count = 0;

        HashSet<Integer> set = new HashSet<>();

        for (Integer element : arr) {
            set.add(element);
        }

        for (Integer element : arr) {
            int previousConsecutiveElement = element - 1;

            if (!set.contains(previousConsecutiveElement)) {

                // Element is the first value of a consecutive sequence.
                int j = element;
                
                while (set.contains(j)) {
                    // The next consecutive element will be j + 1.
                    j++;
                }

                // Update maximum length
                ans = Math.max(ans, j - element);
            }

        }

        return ans;
    }
}

public static void main(String[] args)
    {
        int input[ ] = { 33, 20, 34, 30, 35};
        int n = input.length;
 
        System.out.println(
            "Length of the Longest "
            + "contiguous subsequence is "
            + lenSubsq(input, n));
    }
}
Output: 
Length of the longest continuous subsequence is 3.

Python Solution 

def lenOfConsecutiveSub(arr, n):
    # Storing length of longest consecutive sequence.
    ans = 0
    
    # Storing the length of the current consecutive Sequence.
    count = 0
    
    # Storing all the unique elements of an array.
    sett = set()
    
    for element in arr:
        sett.add(element)
        
    for element in arr:
        
        previousConsecutiveElement=element-1
        
        if(not previousConsecutiveElement in sett):
            
            # Element is the first value of a consecutive sequence.
            j = element
            
            while j in sett:
                
                # The next consecutive element will be j + 1.
                j += 1
            
            # Update maximum length of consecutive subsequence.
            ans = max(ans , j-element)
     
    return ans

  arr = [ 33, 20, 34, 30, 35 ]
  n = len(arr)
 
  print("Length of the Longest consecutive subsequence is",
        lenOfConsecutiveSub(arr, n))
Output: 
Length of the longest continuous subsequence is 4.

The above approach is the most optimized approach for the above problem.

Time complexity: O(N)

Space complexity: O(N)

Frequently Asked Questions

Does the subsequence and subarray of an array indicate the same set of elements?

No! Subsequence and subarray of an array are entirely different things. Subarray contains elements that are present in a continuous fashion in the array, whereas in subsequence, you can put array elements in any order.

Can I find the longest consecutive subsequence of an array without sorting the array?

Yes, you can accomplish this by the second method discussed in this blog, i.e., using hashing.

What is a consecutive sequence?

A consecutive sequence means that all the elements in that sequence are next to one another i.e. can find each next element by adding 1 in the previous element.Forex: 2 3 4 5

Can I store duplicate elements in an unordered set in C++?

No, you can’t do that because the set is implemented in such a way in the standard library that it can only store unique elements.

Key Takeaways

In this blog, you mastered the problem, longest consecutive subsequence. Now try solving it yourself here. You have learned to solve it using the brute force method as well as the optimized way. Remember that while solving a problem, one should always try solving it with brute force, and then it’s advised to move to an optimized method.

Brute force was taking O(N*logN) complexity that’s why we optimized that code to decrease its time complexity. I hope this article must have cleared all your doubts related to this problem. Remember, Knowledge and positivity always increase with sharing. So With whom are you going to share it next?

By: Deeksha Sharma