Java Longest Continuous Sequence in Array

Longest Consecutive subsequence in Java

Here, in this page we will discuss the program to find the longest consecutive subsequence in C++ . We are Given with an array of integers, we need to find the length of the longest sub-sequence such that elements in the sub-sequence are consecutive integers, the consecutive numbers can be in any order.

Method Discussed :

• Method 1 : Brute Force
• Method 2 : Using Hash-map
• Method 3 : Using Priority Queue.

Method 1 (Brute force Approach) :

• First sort the given input array.
• Remove the multiple occurrences of elements, run a loop and keep a count and max (both initially zero).
• Run a loop from 0 to N and if the current element is not equal to the previous (element+1) then set the count to 1 else increase the count.
• Update max with a maximum of count and max.

Run

import java.io.*; import java.util.*; public class Main {     static int findLongestConseqSubseq(int arr[], int n)     {           // Sort the array         Arrays.sort(arr);           int ans = 0, count = 0;                 ArrayList v = new ArrayList();         v.add(10);                 // Insert repeated elements         // only once in the vector         for (int i = 1; i < n; i++)         {             if (arr[i] != arr[i - 1])                 v.add(arr[i]);         }                // Find the maximum length         // by traversing the array         for (int i = 0; i < v.size(); i++)         {               // Check if the current element is             // equal to previous element +1             if (i > 0 && v.get(i) == v.get(i - 1))                 count++;             else                 count = 1;               // Update the maximum             ans = Math.max(ans, count);         }         return ans;     }       // Driver code     public static void main(String[] args)     {         int arr[] = { 1, 9, 3, 10, 4, 20, 2 };         int n = arr.length;           System.out.println(             "Length of the Longest "             + "contiguous subsequence is "             + findLongestConseqSubseq(arr, n));     } }

Output :

Length of the Longest contiguous subsequence is 3

Method 2 :

• First we will create a hash-map.
• Now, iterate over the array for every i-th element check if this element is the starting point of a subsequence. To check this, simply look for arr[i] – 1 in the hash, if not found, then this is the first element a subsequence.
• If this element is the first element, then count the number of elements in the consecutive starting with this element. Iterate from arr[i] + 1 till the last element that can be found.
• If the count is more than the previous longest subsequence found, then update this.

Run

import java.io.*; import java.util.*; class Main {     // consecutive subsequence     static int findLongestConseqSubseq(int arr[], int n)     {          HashSet S = new HashSet();         int ans = 0;           // Hash all the array elements         for (int i = 0; i < n; ++i)             S.add(arr[i]);          // check each possible sequence from the start         // then update optimal length         for (int i = 0; i < n; ++i)         {             // if current element is the starting             // element of a sequence             if (!S.contains(arr[i] - 1))             {                 // Then check for next elements                 // in the sequence                 int j = arr[i];                 while (S.contains(j))                     j++;                  // update  optimal length if this                 // length is more                 if (ans < j - arr[i])                     ans = j - arr[i];             }         }         return ans;     }       // Driver Code     public static void main(String args[])      {          int arr[] = { 1, 9, 3, 10, 4, 20, 2 };         int n = arr.length;         System.out.println(             "Length of the Longest consecutive subsequence is "             + findLongestConseqSubseq(arr, n));     } }                

Output :

Length of the Longest consecutive subsequence is 4                

Method 3 :

In this method we will use priority queue.

• Create a Priority Queue to store the element
• Store the first element in a variable.
• Remove it from the Priority Queue.
• Check the difference between this removed first element and the new peek element
• If the difference is equal to 1 increase count by 1 and repeats step 2 and step 3
• If the difference is greater than 1 set counter to 1 and repeat step 2 and step 3
• if the difference is equal to 0 repeat step 2 and 3
• if counter greater than the previous maximum then store counter to maximum
• Continue step 4 to 7 until we reach the end of the Priority Queue
• Return the maximum value

Run

import java.io.*; import java.util.PriorityQueue; class Main {     static int findLongestConseqSubseq(int arr[], int N)     {           PriorityQueue<Integer> pq             = new PriorityQueue();         for (int i = 0; i < N; i++)         {             // adding element from             // array to PriorityQueue             pq.add(arr[i]);         }                   // Storing the first element         // of the Priority Queue         // This first element is also         // the smallest element         int prev = pq.poll();                   // Taking a counter variable with value 1         int c = 1;                   // Storing value of max as 1         // as there will always be         // one element         int max = 1;           for (int i = 1; i < N; i++)         {             // check if current peek             // element minus previous             // element is greater then             // 1 This is done because             // if it's greater than 1             // then the sequence             // doesn't start or is broken here             if (pq.peek() - prev > 1)             {                 // Store the value of counter to 1                 // As new sequence may begin                 c = 1;                                   // Update the previous position with the                 // current peek And remove it                 prev = pq.poll();             }                           // Check if the previous             //  element and peek are same             else if (pq.peek() - prev == 0)             {                 // Update the previous position with the                 // current peek And remove it                 prev = pq.poll();             }             // if the difference             // between previous element and peek is 1             else             {                 // Update the counter                 // These are consecutive elements                 c++;                                    // Update the previous position                 //  with the current peek And remove it                 prev = pq.poll();             }               // Check if current longest             // subsequence is the greatest             if (max < c)             {                 // Store the current subsequence count as                 // max                 max = c;             }                }             return max;       }            // Driver Code     public static void main(String args[])         throws IOException     {         int arr[] = { 1, 9, 3, 10, 4, 20, 2 };         int n = arr.length;         System.out.println(             "Length of the Longest consecutive subsequence is "             + findLongestConseqSubseq(arr, n));     }      }                

Output :

Length of the Longest consecutive subsequence is 4                

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 150+ courses offered by PrepInsta in One Subscription

holtzeduceir.blogspot.com

Source: https://prepinsta.com/java-program/to-find-longest-consecutive-subsequence/

Share this post