Longest Consecutive Sequence
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.
Also see, Data Structures
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.
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.
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 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)
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.
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
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 CodeStudio.
Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on CodeStudio.
Cheers!
Previous Article 
