Longest Consecutive Sequence

Reet Maggo
Last Updated: May 13, 2022

Introduction

The Longest Consecutive Sequence problems have an integer array, in which we need to find the length of the longest subsequence. The elements in this subsequence must be consecutive integers but can be in any possible order. There can be several approaches to such problems, all of which will be discussed in this article and their complexity analysis. 

Below are a few examples of Longest Consecutive Sequence problems:

Example Problems

Input: arr[] = {11, 9, 3, 10, 4, 20, 12}

 

Output: 4

Explanation: The subsequence 11, 9, 10, 12 is the longest subsequence of consecutive integer elements.

 

Input: arr[] = {95, 41, 56, 94, 44, 91, 93, 92, 43, 32, 42}

 

Output: 5

Explanation: The subsequence 95, 94, 91, 93, 92 is the longest subsequence of consecutive elements.

Now, we will discuss various approaches for such problems: The straightforward or naive approach, the efficient approach, and another approach using a priority queue.

Straight forward Approach

Algorithm

  • First, sort the array.
  • Remove multiple occurrences of elements.
  • Find the longest subarray having consecutive elements. 
  • Make a loop for count and max, both of which were initially zero.
  • The loop is run from the beginning.
  • If the present element is not equal to (previous element+1), the count will be 1. Otherwise, the count will increase.
  • Variable max will be updated with the maximum of count and max. 

Implementation in Java

import java.io.*;
import java.util.*;

class longestConseqSequence {
    static  int findLongest(int arr[],  int n) {

        // Sorting the array
        Arrays.sort(arr);

        int ans =  0, count =  0;
        ArrayList < Integer > v =  new ArrayList < Integer > ();
        v.add(10);

        // Repeated elements inserted only once in the vector
        for (int i =  1; i < n; i++) {
            if (arr[i] != arr[i -  1])
                v.add(arr[i]);
        } 


        // Traversing the array to find the maximum length
        for (int i =  0; i < v.size(); i++) {

            // Comparing current and previous element +1
            if (i >  0 && v.get(i) == v.get(i -  1) +  1)
                count++;
            else
                count =  1;

            // Updating the maximum length
            ans = Math.max(ans, count);
        }
        return ans;
    }

    // calling function
    public  static  void main(String[] args) {
        int arr[] = { 11, 9, 3, 10, 4, 20, 12};
        int n = arr.length;

        System.out.println("The length of the Longest " +  "consecutive subsequence is " + findLongest(arr, n));
    }
}

 

Output:

The length of the longest consecutive subsequence is 4

Complexity Analysis

Time Complexity:

The time complexity for this method will be O(N log N).

This is because constant work is done by the for loop ‘n’ times. Hence, the time complexity of this algorithm is dominated by invoking the sort, which runs in O(N log(N)) time.

Space Complexity:

The space complexity for this method will be O(1).

The space complexity for this method is constant, and no extra space is needed because we have sorted the input array in place. The input array cannot be modified, and we can only use linear space for storing a sorted copy of the array.

Efficient Approach

The problem can also be solved in O(n) time using a more efficient solution, i.e., Hashing. All the elements will be inserted in a set, and then all the possible sets of consecutive subsequences will be checked.

Algorithm

  1. An empty hash is created.
  2. All the array elements are inserted into the hash.
  3. Every element in arr[i] will be treated as follows:
  • Checked if it is the starting point of a subsequence by looking for

(arr[i] – 1) in the hash. If not found, it proves to be the first element of a subsequence.

  • If this element is the first element, the number of elements is counted consecutively, starting with this element. Iteration should occur from arr[i] + 1 till the last element.
  • If the count is greater than the longest subsequence found earlier, then it is updated.

 

Implementation in Java

import java.io.*;
import java.util.*;

class  longestConseqSequence {

    // Maximum length of longest subsequence
    static int  findLongest(int arr[],  int n) {
        HashSet < Integer > S =  new HashSet < Integer > ();
        int ans =  0;

        // loop to hash array elements
        for (int i =  0; i < n; ++i) {
            S.add(arr[i]);
        }

        // checking all possible sequences from beginning
        // next, updating optimal length
        for (int i =  0; i < n; ++i) {

            // if the present element is first element of a sequence
            if (!S.contains(arr[i] -  1)) {

                // checking for next elements
                int j = arr[i];
                while (S.contains(j))
                    j++;

                // update optimal length
                if (ans < j - arr[i])
                    ans = j - arr[i];
            }
        }
        return ans;
    }

    // Calling function
    public static void  main(String args[]) {
        int arr[] = { 11, 9, 3, 10, 4, 20, 12};
        int n = arr.length;
        System.out.println("The length of the Longest consecutive subsequence is " + findLongest(arr, n));
    }
}

 

Output:

The length of the longest consecutive subsequence is 4

Complexity Analysis

Time Complexity

For the efficient approach, the time complexity would be O(n).

Assuming the hash insert and search will take O(1) time, only one traversal is needed, making the time complexity O(n).

 

Space Complexity

The space complexity for the approach is O(n).

Linear space is allocated for the hash table to store the O(n) elements in hashmap, making the space complexity O(n).

Another Approach

Using a Priority Queue, this problem can be solved in O(N log N) time.

Algorithm

  1. To store the element, a Priority Queue will be created.
  2. The first element will be stored in a variable.
  3. The first element will then be removed from the Priority Queue.
  4. The difference between the removed element and the new peek element will be checked.
  5. The count is increased by 1 if the difference is 1. The counter is set to 1 if the difference is greater than 1.
  6. Next, repeat steps 2 and 3.
  7. If the difference is just 0, steps 2 and 3 will be repeated.
  8. If the counter comes out to be greater than the previous maximum, it is stored to the maximum.
  9. Steps 4 to 7 will be continued until the end of the Priority Queue is reached.
  10. The maximum value will be returned.

Implementation in Java

import java.io.*;
import java.util.*;

public class longestConseqSequence {

    // calculate length of longest subsequence
    static  int findLongest(int arr[],  int N) {

        PriorityQueue < Integer > pq =  new PriorityQueue < Integer > ();
        for (int i =  0; i < N; i++) {

            // adding element to PriorityQueue from the array
            pq.add(arr[i]);
        }

        /* storing the first and the smallest element of the
                  PriorityQueue*/
        int prev = pq.poll();

        // some counter variable with the value 1
        int c =  1;

        /* value of max would be 1 since there will always be
                  one element*/
        int  max =  1;

        for (int i =  1; i < N; i++) {

            /*if current peek element is greater than 1, the
            sequence does not start or is broken here*/
            if (pq.peek() - prev >  1) {

                // Storing counter value as 1
                // new sequence might begin
                c =  1;

                /* Update previous position with current peek
                      and remove it */
                prev = pq.poll();
            }


            // check if previous element and peek are the same
            else 
                if (pq.peek() - prev ==  0) {

                    /* update previous position with current peek and
                          remove it */
                    prev = pq.poll();
                }

            /* if difference between previous element and peek
                  is 1 */
            else {

                // Update counter with consecutive elements
                c++;

                /* update previous position with current peek
                      and remove it*/
                prev = pq.poll();
            }


            /* checking if the current longest subsequence is the greatest one*/
            if (max < c) {

                // storing current count as max
                max = c;
            }
        }

        return  max;
    }

    // calling function
    public  static  void main(String args[])
    throws IOException {
        int arr[] = { 11, 9, 3, 10, 4, 20, 12};
        int n = arr.length;
        System.out.println("The length of the Longest consecutive subsequence is " + findLongest(arr, n));
    }
}

 

Output:

The length of the longest consecutive subsequence is 4

Complexity Analysis

Time Complexity:

The time complexity for this method will be O(N log N) as we use a priority queue.

Space Complexity:

The space complexity for this method will be O(N).

Linear space is allocated for maintaining the priority queue.

Frequently Asked Questions

Q1. What is a priority queue?

Ans. A priority queue is quite similar to a regular queue or stack data structure.  It is an abstract data type in which every element has some "priority" associated with it. Elements with higher priority are served before elements with low priority.

Q2. When is HashMap used in Java?

Ans. A HashMap is used in Java when there are unique keys for the data to be stored. We must use Hashmaps to search for items based on a key and when time is essential. HashMap should be avoided when maintaining the same order of items is vital in a collection.

Q3. What are the time and space complexities for solving Longest Consecutive Sequence using hashmap?

Ans. The time and space complexity for the hashmap approach or the efficient approach for Longest Consecutive Sequence is O(n).

Q4. Is HashMap faster or HashSet?

Ans. The HashMap is faster because the values in HashMap are associated with a unique key. On the other hand, HashSet is slower since the member objects are used to calculate the hashcode values, which can be the same for two objects. 

Key takeaways

In this article, we learned about the various approaches to solve the Longest Consecutive Sequence problems in an integer array using examples and code snippets for all three of them. We also discussed the time and space complexity for the straightforward approach, efficient approach and priority queue method to understand how one was better than the other.

You can go to CodeStudio and try solving more problems related to the topic. Share this blog with your friends if you found it helpful! Until then, All the best for your future endeavours, and Keep Coding.

Was this article helpful ?
0 upvotes