Given an array arr[] of non-negative 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[] = [2, 6, 1, 9, 4, 5, 3] Output: 6 Explanation: The consecutive numbers here are 1, 2, 3, 4, 5, 6. These 6 numbers form the longest consecutive subsquence.
Input: arr[] = [1, 9, 3, 10, 4, 20, 2] Output: 4 Explanation: 1, 2, 3, 4 is the longest consecutive subsequence.
Input: arr[] = [15, 13, 12, 14, 11, 10, 9] Output: 7 Explanation: The longest consecutive subsequence is 9, 10, 11, 12, 13, 14, 15, which has a length of 7.
Constraints:
1 <= arr.size() <= 105
0 <= arr[i] <= 105
Approach 01:
-
C++
-
Python
#include <vector> #include <set> #include <algorithm> using namespace std; class Solution { public: // Function to return the length of the longest subsequence of consecutive integers. int longestConsecutive(vector<int>& arr) { set<int> uniqueElements(arr.begin(), arr.end()); vector<int> sortedArray; int maxLength = 0; int currentLength = 1; for (const int &element : uniqueElements) { sortedArray.push_back(element); } for (int index = 1; index < sortedArray.size(); ++index) { if (sortedArray[index - 1] + 1 == sortedArray[index]) { ++currentLength; continue; } maxLength = max(maxLength, currentLength); currentLength = 1; } // Final check in case the longest sequence is at the end maxLength = max(maxLength, currentLength); return maxLength; } };
class Solution: def longestConsecutive(self, arr): uniqueElements = set(arr) sortedArray = sorted(uniqueElements) maxLength = 0 currentLength = 1 for index in range(1, len(sortedArray)): if sortedArray[index - 1] + 1 == sortedArray[index]: currentLength += 1 else: maxLength = max(maxLength, currentLength) currentLength = 1 # Final check in case the longest sequence is at the end maxLength = max(maxLength, currentLength) return maxLength
Time Complexity Analysis
-
Creating the Set
uniqueElements
:- The
std::set
is constructed using the input vectorarr
via its constructor:
set<int> uniqueElements(arr.begin(), arr.end());
- This involves inserting each element of
arr
into theset
. Since aset
uses a balanced binary search tree (e.g., Red-Black Tree) for storage, each insertion operation takes \( O(\log n) \). - If there are \( n \) elements in the array
arr
, the total time complexity for this step is: \( O(n \log n) \).
- The
-
Copying Elements from the Set to the Vector
sortedArray
:- Iterating through all elements of the
set
takes \( O(n) \), where \( n \) is the number of unique elements in the array. - Copying these elements into the vector
sortedArray
also takes \( O(n) \). - Combined time complexity for this step: \( O(n) \).
- Iterating through all elements of the
-
Iterating Through
sortedArray
to Find the Longest Consecutive Subsequence:- The second loop iterates through the
sortedArray
to find the longest consecutive sequence: - This involves one pass over the \( n \) unique elements, making the time complexity: \( O(n) \).
for (int index = 1; index < sortedArray.size(); ++index) { ... }
- The second loop iterates through the
Overall Time Complexity: Adding up all the steps: \( O(n \log n) + O(n) + O(n) = O(n \log n) \)
Space Complexity Analysis
-
Space for the Set
uniqueElements
:- The
set
stores all the unique elements of the input array. In the worst case, all elements inarr
are unique, so the space complexity is: \( O(n) \).
- The
-
Space for the Vector
sortedArray
:- The
sortedArray
vector stores the same \( n \) unique elements as theset
. Hence, this requires: \( O(n) \).
- The
-
Auxiliary Variables:
- The code uses integer variables like
maxLength
andcurrentLength
, which take \( O(1) \) space.
- The code uses integer variables like
set
and vector
, so the total space complexity is: \( O(n) \)