Longest Consecutive Subsequence

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() <= 10⁵
0 <= arr[i] <= 10⁵

Approach 01:

#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 vector arr via its constructor:
    set<int> uniqueElements(arr.begin(), arr.end());
  • This involves inserting each element of arr into the set. Since a set 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) \).

• 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 sortedArray to Find the Longest Consecutive Subsequence:

  • The second loop iterates through the sortedArray to find the longest consecutive sequence:

  for (int index = 1; index < sortedArray.size(); ++index) { ... }

  • This involves one pass over the \( n \) unique elements, making the time complexity: \( O(n) \).

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 in arr are unique, so the space complexity is: \( O(n) \).

• Space for the Vector sortedArray:

  • The sortedArray vector stores the same \( n \) unique elements as the set. Hence, this requires: \( O(n) \).

• Auxiliary Variables:

  • The code uses integer variables like maxLength and currentLength, which take \( O(1) \) space.