Longest Consecutive Sequence

Introduction

A "Longest Consecutive Sequence" refers to a consecutive sequence of numbers within a given set where each number follows the previous one without any gaps. The aim is to find the longest sequence of consecutive numbers within the set.

A 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 the 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:

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

Naive Approach

The naive approach to finding the longest consecutive sequence in an array involves iterating over each element in the array and checking if the next consecutive number is present in the array. If the next consecutive number is present, we continue checking for the next consecutive number until there are no more consecutive numbers. We keep track of the length of the consecutive sequence and update the longest consecutive sequence found so far.

Here is the pseudocode for the naive approach:

int findLongestConsecutiveSequence(vector<int>& nums) {
    int longestSequence = 0;
    for (int num : nums) {
        int currentSequenceLength = 1;
        int currentNum = num;
        while (find(nums.begin(), nums.end(), currentNum + 1) != nums.end()) {
            currentSequenceLength++;
            currentNum++;
        }
        longestSequence = max(longestSequence, currentSequenceLength);
    }
    return longestSequence;
}

In this approach, we iterate over each element in the array, and for each element, we iterate over the array again to find the length of the consecutive sequence starting from that element. The time complexity of this approach is O(n^2), where n is the length of the array. It is not the most efficient approach, but it can be useful for small arrays or as a starting point for more optimized solutions.

Longest Consecutive Subsequence using Sorting without Removing Duplicate Elements:

In this approach, sorting is used without removing any duplicate elements from the array means we will also consider the duplicate elements. Here are the following steps to understand this approach:

Step 1: If the length of the array is 0, return 0. Because the length of the longest consecutive subsequence will also be 0.

Step 2: Sort the given array, and any sorting method can be used here to sort the array.

Step 3: Start an iteration of the array from 1 to n and start comparing the current with the previous element.

Step 4: If both the elements are the same, then continue (skip the elements as these two elements are duplicates).

Step 5: If the difference between the current and previous element is 1, then increment the count of the longest consecutive subsequence and update the max_length to the maximum by comparing it with the count.

Step 6: Else set the count to 1, as the length of the longest consecutive subsequence is broken. So we need to start with 1 from the next element.

Step 7: Return the max_length, as this will store the length of the longest consecutive subsequence.

Let's look at the implementation of the above-explained approach :

C++
Java
Python
C#
Javascript

C++

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

int longestConsecutive(vector < int > & nums) {
   int n = nums.size();
   
   /* if n is 0, length of longest consecutive subsequence will also be 0. */
   if (n == 0) return 0;
   
   // use sort() function to sort the array.
   sort(nums.begin(), nums.end());
   
   /* create two variables, to maintain the count and the maximum length of longest consecutive subsequence */
   int count = 1, max_length = 1;

   // Iteration from 1 to n
   for (int i = 1; i < n; i++) {
       
       // if the current and previous elements are the same, just skip
       if (nums[i] == nums[i - 1]) continue;
       
       /* if the difference of current and previous elements is 1, increment the count and update the value of max_length with the maximum. */
       if (nums[i] - nums[i - 1] == 1) {
           count++;
           max_length = max(count, max_length);
       } 
       
       // Else set the count to 1, and start with 1 from the next element.
       else count = 1;
   }
   
   return max_length;
}

int main() {
   vector <int> input = { 33, 20, 34, 30, 35 };
   
   cout << "Length of Longest Consecutive Subsequence is " << longestConsecutive(input);
   return 0;
}

You can also try this code with Online C++ Compiler

Longest Consecutive Sequence

Introduction

Naive Approach

Longest Consecutive Subsequence using Sorting without Removing Duplicate Elements:

C++

Java

Python

C#

Javascript

Longest Consecutive Subsequence using Hashing:

C++

Java

Python

C#

Javascript

Longest Consecutive Subsequence using Priority Queue:

C++

Java

Python

C#

Javascript

Longest Consecutive Subsequence using Dynamic Programming:

C++

Java

Python

C#

Javascript

Longest Consecutive Subsequence using Hashing:

C++

Java

Python

C#

Javascript

Frequently Asked Questions

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

How does the longest common sequence work?

Can there be more than one longest common subsequence?

How do you find the longest consecutive sequence in an array?

Which is known to be the longest sequence or path?

Conclusion