Ayush Kumar

Longest Consecutive Subsequence

Problem Statement

We are given an unsorted integer array nums, and we have to find the length of the longest consecutive sequence of elements in it.

The order of elements in the array shouldn’t matter as we are looking for a subsequence and not a subarray.

For example, the longest consecutive subsequence in the array [8, 2, 5, 6, 7, 3], is [5, 6, 7, 8].

Note: The algorithm should run in O(n) time, where n is the size of the input array nums.

Example 1:

Input:

Length of nums = 5
nums = [3, 6, 7, 8, 9]

Output:

Length of longest consecutive subsequence in nums = 4

Explanation:

The longest consecutive subsequence in the input array is [6, 7, 8, 9]; therefore, its length is 4.

Example 2:

Input:

Length of nums = 9
nums = [1, 3, 5, -3, -1, 0, 2, 7, 4]

Output:

Length of longest consecutive subsequence in nums: 7

Explanation: The longest consecutive subsequence in the input array is [-1, 0, 1, 2, 3, 4, 5], therefore its length is 7.

Constraints

Approach 1: Brute Force Approach

The Brute Force approach is the most inefficient way in terms of time complexity as in this approach, we will be considering each number in nums and check if that is the part of the longest consecutive subsequence or not.

Algorithm

This algorithm considers each number in the nums array and counts as high as the sequence goes from that. The greatest count recorded is returned as the length of the longest consecutive subsequence.

This is an optimal algorithm as it checks for every possibility and returns an accurate answer.

Implementation (C++ 20, Java 1.8, Python 3)

Implementation in C++ 20

// C++ program to find the longest consecutive sequence in an array
// Brute Force Approach

#include <iostream>
#include <vector>
#include <algorithm>

using std::cin;
using std::cout;
using std::vector;
using std::max;

// Function to find the length of longest consecutive subsequence using brute force approach
int longestConsecutive(vector<int> nums){
    int longest = 0;
    for(auto x: nums){
        int currNum = x;
        int currStreak = 1;

        while(find(nums.begin(), nums.end(), currNum+1) != nums.end()){
            currNum++;
            currStreak++;
        }

        longest = max(currStreak, longest);
    }

    return longest;
}

// Driver code
int main(){
    int n = 5;

    vector<int> nums = {3, 4, 6, 7, 8};
    int ans = longestConsecutive(nums);
    cout<<"Length of longest consecutive subsequence in nums = "<<ans;

    return 0;
}

Implementation in Java 1.8

// Java program to find the longest consecutive sequence in an array
// Brute Force Approach

import java.util.Arrays;
import java.util.Scanner;


public class Main{
    // Function to find the length of longest consecutive subsequence using brute force approach
    public static int longestConsecutive(Integer[] nums){
        int longest = 0;

        for(int x: nums){
            int currNum = x;
            int currStreak = 1;

            while(Arrays.asList(nums).contains(currNum+1)){
                currNum++;
                currStreak++;
            }

            longest = Math.max(longest, currStreak);
        }

        return longest;
    }

    // Driver Code
    public static void main(String[] args){
        int n = 5;

        Integer[] nums = new Integer[n];
        nums[0] = 3;
        nums[1] = 4;
        nums[2] = 6;
        nums[3] = 7;
        nums[4] = 8;

        int ans = longestConsecutive(nums);
        System.out.println("Length of longest consecutive subsequence in nums = " + ans);
    }
}

Implementation in Python 3

# Python program to find the longest consecutive sequence in an array
# Brute Force Approach

# Function to find the length of longest consecutive subsequence using brute force approach
def longestConsecutive(nums):
    longest = 0

    for x in nums:
        currNum = x
        currStreak = 1

        while (currNum+1) in nums:
            currNum += 1
            currStreak += 1

        longest = max(currStreak, longest)

    return longest


# Driver Code
n = 5

nums = [3, 4, 6, 7, 8]

ans = longestConsecutive(nums)
print("Length of longest consecutive subsequence in nums =", ans)

The output for all of the implementations will be the same as the problem and the algorithm are the same.

Output

Length of longest consecutive subsequence in nums = 3

The longest consecutive sequence in the array [3, 4, 6, 7, 8] will be [6, 7, 8].

Complexity analysis

Time Complexity: O(n3)

The for loop in the longestConsecutive() function runs exactly n times and the while loop nested inside it also runs in O(n) time as currNum is getting incremented by 1 in each iteration. Then on each iteration in the while loop, a lookup in the array nums is performed to check if currNum+1 is present in it or not, this also costs O(n) runtime.

Therefore, the runtime of this brute force algorithm is actually the same as three nested O(n) loops.

Space Complexity: O(1)

This algorithm only allocates only a handful of integers that too independent of n.

Approach 2: Naive Approach (Sorting)

This algorithm is what comes to everyone’s mind upon seeing this problem, as it is the simplest to perceive and think of.

The intuition behind this algorithm is that it will be easier to find sequences of consecutive numbers in a sorted array than in an unsorted one.

Algorithm

In this algorithm, we are first sorting the nums array and considering each number to compare to its previous number. To store the longest length recorded and the current length of the subsequence, we will initialize two variables – longest and current.

Now, we will consider each number (except the first, as we need to compare each number to its previous number). If the current number and previous number are equal, then our sequence is neither extended nor broken, and we can simply move to the next number.

If the current number and previous number are unequal, we will check if the current number is one more than the previous (extends the sequence). If it does, then we will add 1 to our current count (current) and move forward, and if it doesn’t, we will store our current count and reset it to 1 (to include the count of the current number that broke the sequence).

In the end, we will return the longest count (longest) as the length of the longest consecutive sequence of nums.

Implementation (C++ 20, Java 1.8, Python 3)

Implementation in C++ 20

// C++ program to find the longest consecutive sequence in an array
// Naive Approach (Sorting)

#include <iostream>
#include <vector>
#include <algorithm>

using std::cin;
using std::cout;
using std::vector;
using std::max;

// Function to find the length of longest consecutive subsequence using sorting
int longestConsecutive(vector<int> nums){
    sort(nums.begin(), nums.end());

    int longest = 0;
    int current = 1;

    for(int i = 1; i < nums.size(); i++){
        if(nums[i] != nums[i-1]) {
            if (nums[i] == nums[i - 1] + 1) {
                current++;
            }
            else {
                longest = max(longest, current);
                current = 1;
            }
        }

        longest = max(current, longest);
    }

    return longest;
}

// Driver code
int main(){
    int n = 7;

    vector<int> nums = {-1, -2, -3, -4, 0, 8, 4};
    int ans = longestConsecutive(nums);
    cout<<"Length of longest consecutive subsequence in nums = "<<ans;

    return 0;
}

Implementation in Java 1.8

// Java program to find the longest consecutive sequence in an array
// Naive Approach (Sorting)

import java.util.Arrays;
import java.util.Objects;
import java.util.Scanner;


public class Main{
    // Function to find the length of longest consecutive subsequence using sorting
    public static int longestConsecutive(Integer[] nums){
        Arrays.sort(nums);

        int longest = 0;
        int current = 1;

        for(int i = 1; i<nums.length; i++){
            if (!Objects.equals(nums[i], nums[i - 1])){
                if(Objects.equals(nums[i],nums[i - 1] + 1))
                    current++;
                else{
                    longest = Math.max(longest, current);
                    current = 1;
                }
            }
        }

        return longest;
    }
    
    // Driver Code
    public static void main(String[] args){
        int n = 7;

        Integer[] nums = new Integer[n];
        nums[0] = -1;
        nums[1] = -2;
        nums[2] = -3;
        nums[3] = -4;
        nums[4] = 0;
        nums[5] = 8;
        nums[6] = 4;
        
        int ans = longestConsecutive(nums);
        System.out.println("Length of longest consecutive subsequence in nums = " + ans);
    }
}

Implementation in Python 3

# Python program to find the longest consecutive sequence in an array
# Naive Approach (Sorting)

# Function to find the length of longest consecutive subsequence using sorting
def longestConsecutive(nums):
    nums.sort()

    longest = 0
    current = 1

    for i in range(1, len(nums)):
        if nums[i] != nums[i-1]:
            if nums[i] == nums[i-1] + 1:
                current += 1
            else:
                longest = max(current, longest)
                current = 1

    return longest


# Driver Code
n = 7

nums = [-1, -2, -3, -4, 0, 8, 4]

ans = longestConsecutive(nums)
print("Length of longest consecutive subsequence in nums =", ans)

The output for all of the implementations will be the same as the problem and the algorithm are the same.

Output

Length of longest consecutive subsequence in nums = 5

The longest consecutive sequence in the array [-1, -2, -3, -4, 0, 8, 4] will be [-4, -3, -2, -1, 0].

Complexity analysis

Time Complexity: O(nlogn)

The for loop inside the longestConsecutive() function runs exactly n times, but it is dominated by the time taken to sort the nums array (O(nlogn). Therefore, the asymptotic time complexity will be O(n)+O(nlogn) i.e., O(nlogn) .

Space Complexity: O(1)
This algorithm only allocates only a handful of integers that are independent of n.

This algorithm is better than the Brute Force algorithm as it has lesser time complexity.

Approach 3: Using a Priority Queue

In this approach, we will be using a priority queue to find the length of the longest subsequence in an array.

Note: A priority queue is a special type of queue in which all the elements are associated with a priority value. In this case, the bigger numbers are a higher priority than the smaller numbers.

Algorithm

At first, we will create an integer priority queue p_nums and copy all the elements of nums to it. A prevprev variable will be initialized and assigned the value at the top of p_nums.

Then we will run a while loop till p_nums becomes empty. Inside the while loop, we will check if the top of p_nums is equal to prev, if yes, the current number will be ignored, and we will move pop out the topmost element. Then we will check if the top of the queue (current number) is l greater than the previous number or not, if yes, our current count will be incremented by l, and the topmost element will be popped out from the queue.

If none of these conditions satisfies, we will simply reset the current count to 1 and assign the topmost element of the queue to the previous number before popping it out from the queue.

We will keep track of the greatest count recorded in each iteration, and after the end of the while loop, the greatest count will be returned as the length of the longest consecutive subsequence of nums.

Note: This algorithm only works with a min-heap priority queue but priority queues in C++ are max-heap by default.

To solve this problem we will initialize our priority queue using the greater<>, our priority queue initialization will look like this:

priority_queue<int, vector<int>, greater<>> var_name;

Here, greater<> is an object class for greater-than equality comparison, which converts max-heap priority queue to min-heap priority queue.

Implementation (C++ 20, Java 1.8, Python 3)

Implementation in C++ 20

// C++ program to find the longest consecutive sequence in an array
// Priority Queue method

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using std::cin;
using std::cout;
using std::vector;
using std::max;
using std::priority_queue;
using std::greater;

// Function to find the length of longest consecutive subsequence using Priority Queue
int longestConsecutive(vector<int>& nums){
    priority_queue<int, vector<int>, greater<>> p_nums;
    for(int &num : nums)
        p_nums.push(num);

    int longest = 0;
    int current = 1;

    int prev = p_nums.top();
    p_nums.pop();

    while(!p_nums.empty()){
        if(p_nums.top() - prev > 1){
            current = 1;
            prev = p_nums.top();
            p_nums.pop();
        }
        else if(p_nums.top() - prev == 0){
            prev = p_nums.top();
            p_nums.pop();
        }
        else{
            current++;
            prev = p_nums.top();
            p_nums.pop();
        }

        longest = max(longest, current);
    }

    return longest;
}

// Driver code
int main(){
    int n = 4;

    vector<int> nums = {0, 2, 3, 5};

    int ans = longestConsecutive(nums);
    cout<<"Length of longest consecutive subsequence in nums = "<<ans;

    return 0;
}

Implementation in Java 1.8

// Java program to find the longest consecutive sequence in an array
// Priority Queue method

import java.util.Arrays;
import java.util.Scanner;
import java.util.PriorityQueue;

public class Main {
    // Function to find the length of longest consecutive subsequence using Priority Queue
    public static int longestConsecutive(Integer[] nums){
        PriorityQueue<Integer> p_nums =new PriorityQueue<Integer>();

        p_nums.addAll(Arrays.asList(nums));

        int longest = 0;
        int current = 1;

        int prev = p_nums.poll();

        while(!p_nums.isEmpty()){
            if(p_nums.peek() - prev > 1){
                current = 1;
                prev = p_nums.poll();
            }
            else if(p_nums.peek() == prev){
                prev = p_nums.poll();
            }
            else{
                current++;
                prev = p_nums.poll();
            }
            longest = Math.max(longest, current);
        }

        return longest;
    }

    // Driver Code
    public static void main(String[] args){
        int n = 4;
        Integer[] nums = new Integer[n];
        nums[0] = 0;
        nums[1] = 2;
        nums[2] = 3;
        nums[3] = 5;
        
        int ans = longestConsecutive(nums);
        System.out.println("Length of longest consecutive subsequence in nums = " + ans);
    }
}

Implementation in Python 3

# Python program to find the longest consecutive sequence in an array
# Priority Queue method

from queue import PriorityQueue

# Function to find the length of longest consecutive subsequence using Priority Queue
def longestConsecutive(nums):
    p_nums = PriorityQueue()
    for x in nums:
        p_nums.put(x)

    longest = 0
    current = 1

    prev = p_nums.get()

    while not p_nums.empty():
        top = p_nums.get()
        p_nums.put(top)

        if top - prev > 1:
            current = 1
            prev = p_nums.get()
        elif top == prev:
            prev = p_nums.get()
        else:
            current += 1
            prev = p_nums.get()

        longest = max(current, longest)

    return longest


# Driver Code
n = 4

nums = [0, 2, 3, 5]

ans = longestConsecutive(nums)
print("Length of longest consecutive subsequence in nums =", ans)

The output for all of the implementations will be the same as the problem and the algorithm are the same.

Output

Length of longest consecutive subsequence in nums = 2

The longest consecutive sequence in the array [0, 2, 3, 5] will be [2, 3].

Complexity analysis

Time Complexity: O(nlogn)

The main while loop in this algorithm runs exactly n time, but inside the while loop, we are also using a priority queue simultaneously, which has a time complexity of O(nlogn). Therefore, the total time complexity will be O(nlogn).

Space Complexity: O(n)
This algorithm has a linear space complexity as a priority queue is maintained throughout the algorithm of size n.

Approach 4: Using a HashSet

Using a HashSet, we can optimize our brute force solution to a great extent! None of our previous solutions has reached O(n) time complexity, but that will not be the case with this approach (making it the only acceptable solution for this problem).

Algorithm

This algorithm is more similar to the brute force approach than any other algorithm as it has only two changes.

  1. The numbers are stored in a HashSet, allowing O(1) lookups.
  2. An attempt to build a sequence from numbers that are already not a part of a longer sequence.

The 2nd point is accomplished by ensuring that the number which precedes the current number by 1 is not present in the HashSet, because if it were present, we would have ignored the current number as that number would have been a part of a longer sequence.

For example, if nums = [4, 3, 2, 6], the longest consecutive sequence will not start from 4 or 3 as they will be a part of the subsequence starting from 2.

Implementation (C++ 20, Java 1.8, Python 3)

Implementation in C++

// C++ program to find the longest consecutive sequence in an array
// HashSet method

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>

using std::cin;
using std::cout;
using std::vector;
using std::max;
using std::unordered_set;

// Function to find the length of longest consecutive subsequence using HashSet
int longestConsecutive(vector<int> nums){
    unordered_set<int> s_nums;
    for(int &num : nums)
        s_nums.insert(num);

    int longest = 0;

    for(int x: s_nums){
        if(s_nums.find(x-1) == s_nums.end()){
            int currNum = x;
            int current = 1;

            while(s_nums.find(currNum+1) != s_nums.end()){
                currNum++;
                current++;
            }

            longest = max(longest, current);
        }
    }

    return longest;
}

// Driver code
int main(){
    int n = 4;

    vector<int> nums = {0, 2, 3, 5};

    int ans = longestConsecutive(nums);
    cout<<"Length of longest consecutive subsequence in nums = "<<ans;

    return 0;
}

Implementation in Java 1.8

// Java program to find the longest consecutive sequence in an array
// HashSet method

import java.util.Arrays;
import java.util.Scanner;
import java.util.HashSet;


public class Main {
    // Function to find the length of longest consecutive subsequence using HashSet
    public static int longestConsecutive(Integer[] nums){
        HashSet<Integer> s_nums = new HashSet<>(Arrays.asList(nums));
        
        int longest = 0;
        int currStreak = 0;
        
        for(int num: nums){
            if(!s_nums.contains(num-1)){
                int currNum = num;
                currStreak = 1;
                
                while(s_nums.contains(currNum+1)){
                    currNum++;
                    currStreak++;
                }
            }
            
            longest = Math.max(longest, currStreak);
        }

        return longest;
    }

    public static void main(String[] args){
        int n = 4;
        Integer[] nums = new Integer[n];
        nums[0] = 0;
        nums[1] = 2;
        nums[2] = 3;
        nums[3] = 5;

        int ans = longestConsecutive(nums);
        System.out.println("Length of longest consecutive subsequence in nums = " + ans);
    }
}

Implementation in Python 3

# Python program to find the longest consecutive sequence in an array
# HashSet method

# Function to find the length of longest consecutive subsequence using HashSet
def longestConsecutive(nums):
    s_nums = set()
    for x in nums:
        s_nums.add(x)

    longest = 0

    for x in s_nums:
        if x - 1 not in s_nums:
            currNum = x
            current = 1

            while currNum + 1 in s_nums:
                currNum += 1
                current += 1

            longest = max(current, longest)

    return longest


# Driver Code
n = 4

nums = [0, 2, 3, 5]

ans = longestConsecutive(nums)
print("Length of longest consecutive subsequence in nums =", ans)

The output for all of the implementations will be the same as the problem and the algorithm are the same.

Output

Length of longest consecutive subsequence in nums = 2

The longest consecutive sequence in the array [0, 2, 3, 5] will be [2, 3].

Complexity analysis

Time Complexity: O(n)
This algorithm appears to be of O(n^2) time complexity due to a nested while loop inside a for loop, but on inspecting closely, it is realized that it is a linear time complexity algorithm as the for loop and the while loop runs for ntimes throughout the algorithm. In other words, the while loop is amortized.

This means that the time complexity of the algorithm is O(n+n), i.e., O(n).

Space Complexity: O(n)
This algorithm has a linear space complexity as a HashSet is maintained throughout the algorithm of n number of elements.

This algorithm is accepted as a solution to the problem and is more efficient than any other algorithm due to its lowest time complexity.

Conclusion

  • The problem was to find the length of the longest consecutive subsequence in an array.
  • We can find the solution by using Brute Force (three nested loops) approach, it is an optimal solution, but it has O(n^3), which is not preferable at all.
  • The Sorting approach can also be used to find the solution, it is more efficient than the brute force approach, but still, it cannot be accepted as a solution due to its high time complexity.
  • The Priority Queue approach works, but that is just unnecessary, first of all, it’s difficult to intuitively come up with this approach, everyone will prefer the sorting approach, and the sorting approach is a more efficient solution of the two (as the sorting approach doesn’t take any auxiliary space).
  • The HashSet is the best solution for this problem as it has the lowest time complexity of all O(n).

FAQs

Q.What is a Priority Queue?

A.A Priority Queue is a special type of a queue data structure. Each of its elements is assigned a priority. Elements with a higher priority are served before the elements with a lower priority.
For example, Java’s implementation of a Priority Queue is min-heap, i.e., smaller numbers are a higher priority than larger numbers, whereas, C++’s implementation of a Priority Queue is max-heap, i.e., larger numbers have a higher priority than smaller numbers.

Q.When are HashMaps used?

A.HashMaps are used when we have unique keys with their values to be stored. We use HashMaps to search for items based on their keys to save time as it has a O(1)O(1) lookup time.

Q.Why only the HashSet solution is accepted by this problem and not other approaches?

A.The HashSet solution is accepted and not the others because only the HashSet solution works with O(n)O(n) time complexity, others have a higher time complexity which doesn’t satisfy the problem’s needs.

Q.What are HashSets?

A.HashSets are an unordered sequence of elements that only contain unique elements. They are called unordered sets in C++ and sets in Python.

Q.Why did we use a HashSet instead of a HashMap in the last approach?

A. We could have used HashMaps in that approach, but the use of HashSet makes much more sense. A HashSet only has unique values, and there is no use of duplicate values in this algorithm. It takes less memory to store the same number of elements in a HashSet than in a HashMap, as a Hashmap requires two objects for every element (key and value).

Author