Introduction
In this blog, you learn to solve the problem of the Longest Consecutive Subsequence. But before that, you need to be very clear about the definition of subsequence. Most people remain confused between subarray and subsequence, so let’s discuss them first.
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:
1 | 9 | 3 | 10 | 4 | 20 | 2 |
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 with C++ code:
#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;
}
Output:
Longest Consecutive Subsequence 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 ans if this count is greater than the previous one.
Let’s understand it better using code.
Also checkout HashSet.
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)
Longest Consecutive Subsequence using Priority Queue:
In this approach, Priority Queue will be used to find the length of the longest consecutive subsequence. 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: Create a min heap, that will store the top element as the minimum and we can retrieve this minimum element anytime.
Step 3: Start an iteration from 0 to n and insert every element in min heap (or priority queue).
Step 4: After the above iteration, start another loop to iterate the min heap until it gets empty. In this loop, we will retrieve the minimum element (top element of the min heap) and pop it. And compare the current element (top of the min heap) and retrieved element.
Step 5: If both the elements are the same, then continue (skip the elements as these two elements are duplicates).
Step 6: 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 7: 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 8: 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 with C++ code:
#include <bits/stdc++.h>
using namespace std;
int longestConsecutive(vector<int> & nums) {
int n = nums.size();
// if n is 0, return 0 as the length of longest consecutive will be 0.
if (n == 0) return 0;
// create a min heap where the minimum element will have the highest prioriy.
priority_queue <int, vector <int>, greater <int>> pq;
/* create two variables, to maintain the count and the maximum length of longest consecutive subsequence */
int count = 1, max_length = 1;
/* start an iteration from 0 to n, and push the elements in priority queue. */
for (int i = 0; i < n; i++)
pq.push(nums[i]);
// start an iteration till the priority queue gets empty.
while (!pq.empty()) {
// retrieve the minimum element using top() method.
int x = pq.top();
// remove this minimum element from priority queue using pop() method.
pq.pop();
/* now if the difference betweent the current minimum (top of pq) and x is 1, then increment the count. */
if (pq.top() - x == 1)
count++;
// if both the elements are the same, skip.
else if (x == pq.top())
continue;
// else set the count to 1 and start with 1 from the next element.
else
count = 1;
// update the max_length with the maximum length.
max_length = max(max_length, count);
}
return max_length;
}
int main() {
vector <int> input = { 33, 20, 34, 30, 35 };
cout << "Length of Longest Consecutive Subsequence is " << longestConsecutive(input);
return 0;
}
Output:
Longest Consecutive Subsequence using Dynamic Programming:
In this approach, we will use dynamic programming method to find the length of longest consecutive subsequence. Here are the following steps to understand this approach:
Step 1: Create a map of <int, int> and this map will be considered as the Dynamic Programming array that stores the solutions.
Step 2: Iteration will be made from 0 to n and initially for every element, we will store 1 as the count in the seq (DP array).
Step 3: One more iteration will be made from 0 to n, where the max_length will be updated with value given by the populateSeq function. Now let's move in to the populateSeq function.
Step 4: If the current element's solution is not present in seq, return 0.
Step 5: Else If the solution is present, return 1.
Step 6: Else find the solution for the element + 1. Add the found solution in current's solution.
Step 7: Return the solution for current element.
Let's look at the implementation of the above-explained approach with C++ code:
#include <bits/stdc++.h>
using namespace std;
/* seq is the map that we are using as a dp array, to use it in overlapping situations */
unordered_map<int, int> seq;
int populateSeq(int x) {
/* if the current element's solution is not present in seq, return 0. */
if (seq.find(x) == seq.end())
return 0;
// if the solution is present, return it.
if (seq[x] != 1)
return seq[x];
// else find the solution for the element + 1
int p = populateSeq(x + 1);
// add the found solution in current's solution.
seq[x] += p;
return seq[x];
}
int longestConsecutive(vector<int> & nums) {
int n = nums.size(), max_length = 0;
// initially, assign all the elements with count 1.
for (int i = 0; i < n; i++)
seq[nums[i]] = 1;
// iterate 0 to n and find the maximum solution for each element.
for (int i = 0; i < n; i++)
max_length = max(max_length, populateSeq(nums[i]));
return max_length;
}
int main() {
vector<int> input = { 33, 20, 34, 30, 35 };
cout << "Length of Longest Consecutive Subsequence is " << longestConsecutive(input);
return 0;
}
Output:
Frequently Asked Questions
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.
How does the longest common sequence work?
In a given sorted array, numbers are 2, 3, 4, and 5. Here the difference between the 2 consecutive numbers is 1 then there is a common sequence and if there are more than 2 elements, then we can find the longest common sequence.
Can there be more than one longest common subsequence?
Yes there can multiple common subsequence in the array but in the context of problem, we consider only the length of the longest common subsequence.
Conclusion
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.
Recommended Problems -
Recommended Reading:
- Introduction to Hashing
- HashMap
- Longest Subarray Not Having More than K direct Elements
- Hash Table v/s STL Map
- N Repeated Elements in size of 2N
- Kth Distinct String in an Array
- Love Babbar DSA Sheet
- Striver SDE Sheet Problems
- Array in Java
Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests, Test Series, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.
Cheers!