Longest Consecutive Subsequence using Hashing
The idea is to use Hashing. We first insert all elements in a Set. Then check all the possible starts of consecutive subsequences.
Illustration:
Below image is the dry run for example arr[] = {1, 9, 3, 10, 4, 20, 2}:
Follow the steps below to solve the problem:
- Create an empty hash.
- Insert all array elements to hash.
- Do the following for every element arr[i]
- 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 of 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.
Below is the implementation of the above approach:
// C++ program to find longest
// contiguous subsequence
#include <bits/stdc++.h>
using namespace std;
// Returns length of the longest
// contiguous subsequence
int findLongestConseqSubseq(int arr[], int n)
{
unordered_set<int> S;
int ans = 0;
// Hash all the array elements
for (int i = 0; i < n; i++)
S.insert(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.find(arr[i] - 1) == S.end()) {
// Then check for next elements
// in the sequence
int j = arr[i];
while (S.find(j) != S.end())
j++;
// update optimal length if
// this length is more
ans = max(ans, j - arr[i]);
}
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 9, 3, 10, 4, 20, 2 };
int n = sizeof arr / sizeof arr[0];
cout << "Length of the Longest contiguous subsequence "
"is "
<< findLongestConseqSubseq(arr, n);
return 0;
}
// Java program to find longest
// consecutive subsequence
import java.io.*;
import java.util.*;
class ArrayElements {
// Returns length of the longest
// consecutive subsequence
static int findLongestConseqSubseq(int arr[], int n)
{
HashSet<Integer> S = new HashSet<Integer>();
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));
}
}
// This code is contributed by Aakash Hasija
# Python program to find longest contiguous subsequence
def findLongestConseqSubseq(arr, n):
s = set()
ans = 0
# Hash all the array elements
for ele in arr:
s.add(ele)
# check each possible sequence from the start
# then update optimal length
for i in range(n):
# if current element is the starting
# element of a sequence
if (arr[i]-1) not in s:
# Then check for next elements in the
# sequence
j = arr[i]
while(j in s):
j += 1
# update optimal length if this length
# is more
ans = max(ans, j-arr[i])
return ans
# Driver code
if __name__ == '__main__':
n = 7
arr = [1, 9, 3, 10, 4, 20, 2]
print("Length of the Longest contiguous subsequence is ",
findLongestConseqSubseq(arr, n))
# Contributed by: Harshit Sidhwa
using System;
using System.Collections.Generic;
// C# program to find longest consecutive subsequence
public class ArrayElements {
// Returns length of the
// longest consecutive subsequence
public static int findLongestConseqSubseq(int[] arr,
int n)
{
HashSet<int> S = new HashSet<int>();
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 = new int[] { 1, 9, 3, 10, 4, 20, 2 };
int n = arr.Length;
Console.WriteLine(
"Length of the Longest consecutive subsequence is "
+ findLongestConseqSubseq(arr, n));
}
}
// This code is contributed by Shrikant13
// Javascript program to find longest
// contiguous subsequence
// Returns length of the longest
// contiguous subsequence
function findLongestConseqSubseq(arr, n) {
let S = new Set();
let ans = 0;
// Hash all the array elements
for (let i = 0; i < n; i++)
S.add(arr[i]);
// check each possible sequence from
// the start then update optimal length
for (let i = 0; i < n; i++)
{
// if current element is the starting
// element of a sequence
if (!S.has(arr[i] - 1))
{
// Then check for next elements
// in the sequence
let j = arr[i];
while (S.has(j))
j++;
// update optimal length if
// this length is more
ans = Math.max(ans, j - arr[i]);
}
}
return ans;
}
// Driver code
let arr = [1, 9, 3, 10, 4, 20, 2];
let n = arr.length;
console.log("Length of the Longest contiguous subsequence is "
+ findLongestConseqSubseq(arr, n));
// This code is contributed by gfgking.
Output
Length of the Longest contiguous subsequence is 4
Time complexity: O(N), Only one traversal is needed and the time complexity is O(n) under the assumption that hash insert and search takes O(1) time.
Auxiliary space: O(N), To store every element in the hashmap O(n) space is needed
Longest Consecutive Subsequence
Given an array of 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[] = {1, 9, 3, 10, 4, 20, 2}
Output: 4
Explanation: The subsequence 1, 3, 4, 2 is the longest subsequence of consecutive elementsInput: arr[] = {36, 41, 56, 35, 44, 33, 34, 92, 43, 32, 42}
Output: 5
Explanation: The subsequence 36, 35, 33, 34, 32 is the longest subsequence of consecutive elements.
Naive Approach:
The idea is to first sort the array and find the longest subarray with consecutive elements. After sorting the array and removing the multiple occurrences of elements, run a loop and keep a count and max (both initially zero). Run a loop from start to end 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.
Follow the steps below to solve the problem:
- Intialise ans and countConsecutive with 0.
- Sort the arr[].
- Store the distinct elements in dist[] array by traversing over the arr[].
- Now, traverse on the dist[] array to find the count of consecutive elements and maintain the answer variable.
Below is the implementation of above approach:
// C++ program to find longest
// contiguous subsequence
#include <bits/stdc++.h>
using namespace std;
// Returns length of the longest
// contiguous subsequence
int findLongestConseqSubseq(int arr[], int n)
{
int ans = 0, count = 0;
// sort the array
sort(arr, arr + n);
vector<int> v;
v.push_back(arr[0]);
// insert repeated elements only once in the vector
for (int i = 1; i < n; i++) {
if (arr[i] != arr[i - 1])
v.push_back(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[i] == v[i - 1] + 1)
count++;
// reset the count
else
count = 1;
// update the maximum
ans = max(ans, count);
}
return ans;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 2, 3 };
int n = sizeof arr / sizeof arr[0];
cout << "Length of the Longest contiguous subsequence "
"is "
<< findLongestConseqSubseq(arr, n);
return 0;
}
// Java program to find longest
// contiguous subsequence
import java.io.*;
import java.util.*;
class GFG {
static int findLongestConseqSubseq(int arr[], int n)
{
// Sort the array
Arrays.sort(arr);
int ans = 0, count = 0;
ArrayList<Integer> v = new ArrayList<Integer>();
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) + 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));
}
}
// This code is contributed by parascoding
# Python3 program to find longest
# contiguous subsequence
# Returns length of the longest
# contiguous subsequence
def findLongestConseqSubseq(arr, n):
ans = 0
count = 0
# Sort the array
arr.sort()
v = []
v.append(arr[0])
# Insert repeated elements only
# once in the vector
for i in range(1, n):
if (arr[i] != arr[i - 1]):
v.append(arr[i])
# Find the maximum length
# by traversing the array
for i in range(len(v)):
# Check if the current element is
# equal to previous element +1
if (i > 0 and v[i] == v[i - 1] + 1):
count += 1
# Reset the count
else:
count = 1
# Update the maximum
ans = max(ans, count)
return ans
# Driver code
arr = [1, 2, 2, 3]
n = len(arr)
print("Length of the Longest contiguous subsequence is",
findLongestConseqSubseq(arr, n))
# This code is contributed by avanitrachhadiya2155
// C# program to find longest
// contiguous subsequence
using System;
using System.Collections.Generic;
class GFG {
static int findLongestConseqSubseq(int[] arr, int n)
{
// Sort the array
Array.Sort(arr);
int ans = 0, count = 0;
List<int> v = new List<int>();
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.Count; i++) {
// Check if the current element is
// equal to previous element +1
if (i > 0 && v[i] == v[i - 1] + 1)
count++;
else
count = 1;
// Update the maximum
ans = Math.Max(ans, count);
}
return ans;
}
// Driver code
static void Main()
{
int[] arr = { 1, 9, 3, 10, 4, 20, 2 };
int n = arr.Length;
Console.WriteLine(
"Length of the Longest "
+ "contiguous subsequence is "
+ findLongestConseqSubseq(arr, n));
}
}
// This code is contributed by divyeshrabadiya07
// JavaScript program to find longest
// contiguous subsequence
// Returns length of the longest
// contiguous subsequence
function findLongestConseqSubseq(arr, n) {
let ans = 0, count = 0;
// sort the array
arr.sort(function (a, b) { return a - b; })
var v = [];
v.push(arr[0]);
//insert repeated elements only once in the vector
for (let i = 1; i < n; i++) {
if (arr[i] != arr[i - 1])
v.push(arr[i]);
}
// find the maximum length
// by traversing the array
for (let i = 0; i < v.length; i++) {
// Check if the current element is equal
// to previous element +1
if (i > 0 && v[i] == v[i - 1] + 1)
count++;
// reset the count
else
count = 1;
// update the maximum
ans = Math.max(ans, count);
}
return ans;
}
// Driver code
let arr = [1, 2, 2, 3];
let n = arr.length;
console.log(
"Length of the Longest contiguous subsequence is "
+findLongestConseqSubseq(arr, n)
);
// This code is contributed by Potta Lokesh
Output
Length of the Longest contiguous subsequence is 3
Time complexity: O(Nlog(N)), Time to sort the array is O(Nlog(N)).
Auxiliary space: O(N). Extra space is needed for storing distinct elements.