Longest Consecutive
Subsequence
Given an array of integers, find the length of the longest
sub-sequence such that elements in the subsequence are
consecutive integers, the consecutive 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 :
The idea is to first sort the array and find the longest subarray with
consecutive elements. After sorting the array and removing the
multiple occurrences of elements, run a loop and keep a count and
max (both initially zero). Run a loop from start to end and if the
current element is not equal to the previous (element+1) then set the
count to 1 else increase the count. Update max with a maximum of
count and max.
Follow the steps below to solve the problem:
Intialise ans and countConsecutive with 0.
Sort the arr[].
Store the distinct elements in dist[] array by traversing over the
arr[].
Now, traverse on the dist[] array to find the count of consecutive
elements and maintain the answer variable.
Below is the implementation of above approach:
// 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;
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.
Longest Consecutive Subsequence using
Hashing:
The idea is to use Hashing. We first insert all elements in a Set. Then
check all the possible starts of consecutive subsequences.
Illustration:
Below image is the dry run for example arr[] = {1, 9, 3, 10, 4, 20, 2}:
Follow the steps below to solve the problem:
Create an empty hash.
Insert all array elements to hash.
Do the following for every element arr[i]
Check if this element is the starting point of a subsequence. To check this,
simply look for arr[i] – 1 in the hash, if not found, then this is the first
element of a subsequence.
If this element is the first element, then count the number of elements in
the consecutive starting with this element. Iterate from arr[i] + 1 till the
last element that can be found.
If the count is more than the previous longest subsequence found, then
update this.
Below is the implementation of the above approach:
// 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)
{
unordered_set<int> S;
int ans = 0;
// Hash all the array elements
for (int i = 0; i < n; i++)
S.insert(arr[i]);
// check each possible sequence from
// the start then update optimal length
for (int i = 0; i < n; i++) {
// if current element is the starting
// element of a sequence
if (S.find(arr[i] - 1) == S.end()) {
// Then check for next elements
// in the sequence
int j = arr[i];
while (S.find(j) != S.end())
j++;
// update optimal length if
// this length is more
ans = max(ans, j - arr[i]);
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 9, 3, 10, 4, 20, 2 };
int n = sizeof arr / sizeof arr[0];
cout << "Length of the Longest contiguous
subsequence "
"is "
<< findLongestConseqSubseq(arr, n);
return 0;
}
Output
Length of the Longest contiguous subsequence is 4
Time complexity: O(N), Only one traversal is needed and the
time complexity is O(n) under the assumption that hash insert
and search takes O(1) time.
Auxiliary space: O(N), To store every element in the hashmap
O(n) space is needed
Longest Consecutive Subsequence using
Priority Queue:
The Idea is to use Priority Queue. Using priority queue it will sort the
elements and eventually it will help to find consecutive elements.
Illustration:
Input: arr[] = {1, 9, 3, 10, 4, 20, 2}
Insert all the elements in the Priority Queue:
1 2 3 4 9 10 20
Initialise variable prev with first element of priority queue, prev will
contain last element has been picked and it will help to check whether
the current element is contributing for consecutive sequence or not.
prev = 1, countConsecutive = 1, ans = 1
Run the algorithm till the priority queue becomes empty.
2 3 4 9 10 20
current element is 2
prev + 1 == 2, therefore increment countConsecutive by 1
countConsecutive = countConsecutive + 1 = 1 + 1 = 2
update prev with current element, prev = 2
pop the current element
ans = max(ans, countConsecutive) = (1, 2) = 2
3 4 9 10 20
current element is 3
prev + 1 == 3, therefore increment countConsecutive by 1
countConsecutive = countConsecutive + 1 = 2 + 1 = 3
update prev with current element, prev = 3
pop the current element
ans = max(ans, countConsecutive) = (2, 3) = 3
4 9 10 20
current element is 4
prev + 1 == 4, therefore increment countConsecutive by 1
countConsecutive = countConsecutive + 1 = 3 + 1 = 4
update prev with current element, prev = 4
pop the current element
ans = max(ans, countConsecutive) = (3, 4) = 4
9 10 20
current element is 9
prev + 1 != 9, therefore re-initialise countConsecutive by 1
countConsecutive = 1
update prev with current element, prev = 9
pop the current element
ans = max(ans, countConsecutive) = (4, 1) = 4
10 20
current element is 10
prev + 1 == 10, therefore increment countConsecutive by 1
countConsecutive = countConsecutive + 1 = 1 + 1 = 2
update prev with current element, prev = 10
pop the current element
ans = max(ans, countConsecutive) = (4, 2) =4
20
current element is 20
prev + 1 != 20, therefore re-initialise countConsecutive by 1
countConsecutive = 1
update prev with current element, prev = 20
pop the current element
ans = max(ans, countConsecutive) = (4, 1) = 4
Hence, the longest consecutive subsequence is 4.
Follow the steps below to solve the problem:
1. Create a Priority Queue to store the element
2. Store the first element in a variable
3. Remove it from the Priority Queue
4. Check the difference between this removed first element and the
new peek element
5. If the difference is equal to 1 increase the count by 1 and repeats
step 2 and step 3
6. If the difference is greater than 1 set counter to 1 and repeat step 2
and step 3
7. if the difference is equal to 0 repeat step 2 and 3
8. if counter greater than the previous maximum then store counter to
maximum
9. Continue step 4 to 7 until we reach the end of the Priority Queue
10. Return the maximum value
Below is the implementation of the above approach:
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
int findLongestConseqSubseq(int arr[], int N)
{
priority_queue<int, vector<int>, greater<int> > pq;
for (int i = 0; i < N; i++) {
// adding element from
// array to PriorityQueue
pq.push(arr[i]);
}
// Storing the first element
// of the Priority Queue
// This first element is also
// the smallest element
int prev = pq.top();
pq.pop();
// Taking a counter variable with value 1
int c = 1;
// Storing value of max as 1
// as there will always be
// one element
int max = 1;
while (!pq.empty()) {
// check if current peek
// element minus previous
// element is greater than
// 1 This is done because
// if it's greater than 1
// then the sequence
// doesn't start or is broken here
if (pq.top() - prev > 1) {
// Store the value of counter to 1
// As new sequence may begin
c = 1;
// Update the previous position with the
// current peek And remove it
prev = pq.top();
pq.pop();
}
// Check if the previous
// element and peek are same
else if (pq.top() - prev == 0) {
// Update the previous position with the
// current peek And remove it
prev = pq.top();
pq.pop();
}
// If the difference
// between previous element and peek is 1
else {
// Update the counter
// These are consecutive elements
c++;
// Update the previous position
// with the current peek And remove it
prev = pq.top();
pq.pop();
// Check if current longest
// subsequence is the greatest
if (max < c) {
// Store the current subsequence count as
// max
max = c;
}
}
return max;
// Driver Code
int main()
{
int arr[] = { 1, 9, 3, 10, 4, 20, 2 };
int n = 7;
cout << "Length of the Longest consecutive
subsequence "
"is "
<< findLongestConseqSubseq(arr, n);
return 0;
Output
Length of the Longest consecutive subsequence is 4
Time Complexity: O(N*log(N)), Time required to push and pop
N elements is logN for each element.
Auxiliary Space: O(N), Space required by priority queue to
store N elements.
