Finding the longest consecutive subsequence

Today we gonna discuss the problem of finding the longest consecutive subsequence from a given array.

To understand this problem, just consider this array of numbers.

Now you need to find a subsequence such that numbers in it are consecutive and no matter what their order is.

The basic way to solve this problem is by picking each number starting from the first number of the array and look for its next and previous consecutive numbers in the whole array.

Let’s say for this array [7 3 5 10 4], we pick the first number i.e 7, and now we look for its next consecutive number 8 in the whole array.

If it is not there, we then start looking for its previous consecutive number 6 in the whole array.

But unfortunately it is also not present in the array.

So you can see 7 cannot be part of any consecutive subsequence for this array.

And longest consecutive subsequence count for this array till now is 1, which is 7 itself.

Now we move to next element i.e 3, and look for next consecutive number 4 in this whole array.

If we are able to find it, we again try to find the next consecutive number 5 in this whole array and so on till there is no next consecutive number.

There is one more thing which I forgot is that

we can also find min and max value from this array, which will help us to define upper and lower boundary while finding the consecutive numbers.

ok

After finding all the forward consecutive numbers for 3 which is 4 & 5, we start looking for previous consecutive number 2 in this whole array.

But as you can see 3 is the smallest number in this given array, so there is no need to look backward.

Now our longest consecutive subsequence count for this array till now is changed to 3 i.e 3, 5 & 4

So we can move in this pattern to find the longest consecutive subsequence.

But you can observe that this is not the efficient way to solve this problem, because you need to traverse each element to find the next and previous

consecutive number.

Hmmm, so can you think of which part of this solution we discussed can be made efficient.

Yes, we can reduce the look up time for next and previous consecutive number for each element by using HashMap.

So we will start by putting each number in a HashMap.

Now we will pick each number from the array and try to find its next and previous consecutive number using hash map.

So in this way we will be able to find longest consecutive subsequence in an efficient way.