Techie Delight
Coding made easy
Given an array of integers, find the length of longest subsequence formed by the consecutive integers. The subsequence should contain all distinct values and the character set should be consecutive, irrespective of its order.
The problem differs from finding largest sub-array formed by the consecutive integers. Unlike subarrays, subsequences are not required to occupy consecutive positions within the original sequences.
For example, consider array { 2, 0, 6, 1, 5, 3, 7 }. The largest subsequence formed by the consecutive integers is { 2, 0, 1, 3 }.
Naive solution is to sort the array in ascending order and compare the consecutive elements to find the maximum length sub-array with consecutive integers. The time complexity of this solution would be O(nlog(n)).
We can do better using Hashing. The idea is to consider each element of the input sequence and find the maximum length consecutive subsequence starting with it. i.e. for every element e, we check for presence of elements e+1, e+2, e+3.. in the input. We can optimize the code by using set for constant time lookups to determine if the element present in the input sequence or not.
The algorithm can be implemented as below in C++, Java and Python:
C++
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
// Function to find the length of largest subsequence formed by consecutive integers
int findMaxLenSubSeq(vector<int> &vec)
{
// construct a set out of input elements
unordered_set<int> S(vec.begin(), vec.end());
// initialize result by 1
int max_len = 1;
// do for each element of the input sequence
for (int e: vec)
{
// check if current element e is candidate for starting of a sequence
// i.e. previous element (e – 1) don’t exist in the set
if (S.find(e – 1) == S.end())
{
// len stores the length of subsequence starting with current element
int len = 1;
// check for presence of elements e+1, e+2, e+3.. e+len in the set
while (S.find(e + len) != S.end())
len++;
// update the result with the length of current consecutive subsequence
max_len = max(max_len, len);
}
}
// return result
return max_len;
}
int main()
{
vector<int> vec = { 2, 0, 6, 1, 5, 3, 7 };
cout << “The length of maximum length consecutive subsequence is “
<< findMaxLenSubSeq(vec);
return 0;
}
|
Output:
The length of maximum length consecutive subsequence is 4
Java
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
class Main
{
// Function to find the length of largest subsequence formed by consecutive integers
public static int findMaxLenSubSeq(int[] arr)
{
// construct a set out of input elements
Set<Integer> S = IntStream.of(arr) // returns IntStream
.boxed()
.collect(Collectors.toSet());
// initialize result by 1
int maxLen = 1;
// do for each element of the input sequence
for (int e: arr)
{
// check if current element e is candidate for starting of a sequence
// i.e. previous element (e – 1) don’t exist in the set
if (!S.contains(e – 1))
{
// len stores the length of subsequence starting with current element
int len = 1;
// check for presence of elements e+1, e+2, e+3.. e+len in the set
while (S.contains(e + len)) {
len++;
}
// update the result with the length of current consecutive subsequence
maxLen = Math.max(maxLen, len);
}
}
// return result
return maxLen;
}
public static void main (String[] args)
{
int[] arr = { 2, 0, 6, 1, 5, 3, 7 };
System.out.println(“The length of maximum length consecutive subsequence is “ +
findMaxLenSubSeq(arr));
}
}
|
Output:
The length of maximum length consecutive subsequence is 4
Python
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
# Function to find the length of largest subsequence formed by consecutive integers
def findMaxLenSubSeq(A):
# construct a set out of input elements
S = set(A)
# initialize result by 1
maxlength = 1
# do for each element of the input sequence
for e in A:
# check if current element e is candidate for starting of a sequence
# i.e. previous element (e – 1) don’t exist in the set
if (e – 1) not in S:
# len stores the length of subsequence starting with current element
len = 1
# check for presence of elements e+1, e+2, e+3.. e+len in the set
while (e + len) in S:
len += 1
# update the result with the length of current consecutive subsequence
maxlength = max(maxlength, len)
# return result
return maxlength
if __name__ == ‘__main__’:
A = [2, 0, 6, 1, 5, 3, 7]
print(“The length of maximum length consecutive subsequence is:”,
findMaxLenSubSeq(A))
|
Output:
The length of maximum length consecutive subsequence is 4
Download Run Code
Output:
The length of maximum length consecutive subsequence is 4
Download Run Code
Output:
The length of maximum length consecutive subsequence is 4
Download Run Code
Output:
The length of maximum length consecutive subsequence is 4
The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).
Exercise: Extend the solution to print the maximum length consecutive subsequence.
I think your optimized solution has worse runtime complexity than the simply sorting the list. in case a list already in sorted order, your code will require 1 + 2 + 3 + 4 + ….. +n lookups, which is (n2), which is a lot worse than n(logn)
Note that we’re calling the while loop only when the current element is candidate for starting of a sequence. The time complexity remains O(n).
Good point. Thanks. Love the content.
The ‘Hashing’ solution is incorrect, since there is no sense of ‘consecutive’.
Try:
“vector vec = { 2, 4, 0, 6, 1, 5, 3, 7 };”
It’s correct. The length of maximum length consecutive subsequence is 8 which is formed by {2, 4, 0, 6, 1, 5, 3, 7} whose character set [0-7] is consecutive.
0,1,2,3,4,5,6,7 is not a *subsequence* of the original sequence.
No, the subsequence is {2, 4, 0, 6, 1, 5, 3, 7} whose digits are consecutive “irrespective” of their order.
Ah I see, I missed the ‘irrespective of order’ part. Thanks.
What about elements are in decreasing order…I think it will be n2.
The ascending or descending order doesn’t matter. A set is constructed out of the input elements.
Enter your email address to subscribe to new posts and receive notifications of new posts by email.