PROBLEM DESCRIPTION
Given an array of non-negative 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.
SOLUTION
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
class Solution
{
// arr[] : the input array
// N : size of the array arr[]
//Function to return length of longest subsequence of consecutive integers.
static int findLongestConseqSubseq(int arr[], int n)
{
int maxLength = 0;
Set<Integer> set = new HashSet<>();
for(Integer x: arr){
set.add(x);
}
for(int i=0; i<n; i++){
// MAIN OPTIMIZATION:
// x = arr[i]
// if array contains x-1,
// the longest sequence cannot start from x
// we will start counting only if we get the starting position
if(set.contains(arr[i]-1))
continue;
int len = 0;
int current = arr[i];
while(set.contains(current)){
len++;
current++;
}
maxLength = Math.max(maxLength, len);
}
return maxLength;
}
}