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:
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 :
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; }
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.
C++ #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; }
You can also try this code with Online C++ Compiler
Length of maximum consecutive subsequence will be 3.
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 code implementation:
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, 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; }
You can also try this code with Online C++ Compiler
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 code implementation:
C++
Java
Python
C#
Javascript
C++
#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; }
You can also try this code with Online C++ Compiler
Step 1: Store all the elements of the array in a hash set. Step 2: Iterate through each element of the array. Step 3: For each element, check if it's the start of a sequence (i.e., check if element - 1 is not in the hash set). Step 4: If it's the start, count the number of consecutive elements present in the hash set starting from this element. Step 5: Keep track of the maximum length of such consecutive sequences. Step 6: Return the maximum length.
C++
Java
Python
C#
Javascript
C++
#include <iostream> #include <unordered_set> #include <vector> using namespace std; int findLongestConseqSubseq(vector<int>& arr) { unordered_set<int> S; int ans = 0; // Hash all the array elements for (int i = 0; i < arr.size(); i++) { S.insert(arr[i]); } // Check each possible sequence from the start for (int i = 0; i < arr.size(); i++) { if (S.find(arr[i] - 1) == S.end()) { int j = arr[i]; while (S.find(j) != S.end()) { j++; } // Update optimal length ans = max(ans, j - arr[i]); } } return ans; } int main() { vector<int> arr = {1, 9, 3, 10, 4, 20, 2}; cout << "Length of the Longest consecutive subsequence is " << findLongestConseqSubseq(arr) << endl; return 0; }
You can also try this code with Online C++ Compiler
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.
How do you find the longest consecutive sequence in an array?
To find the longest consecutive sequence in an array, you can iterate through the array, keeping track of the current sequence length and the maximum sequence length encountered so far.
Which is known to be the longest sequence or path?
In various contexts, the longest sequence or path refers to the sequence or path within a dataset, graph, or other structures that has the greatest number of elements or vertices between its starting and ending points.
Conclusion
In this blog, we have discussed the longest consecutive sequence problem. Understanding and implementing algorithms to find the longest consecutive sequence in an array offers valuable insights into efficient problem-solving techniques. By employing strategies such as sorting, hashing, or utilizing sets, programmers can tackle diverse scenarios with varying complexities.
Brute force was taking O(N*logN) complexity thatâ€™s why we optimized that code to decrease its time complexity.