Longest Consecutive Sequence

Given an array of integers. 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.

If you are here then chances are you’re trying to find the longest consecutive sequence in an array of integers. The problem can be visualized as follows:

Source: GeeksForGeeks

The above problem could have multiple solutions, but here we will be using a simple approach with O(N) complexity. Here, we will use Tree-Set from Java Collections which are set but store the values in their natural order by sorting them internally at the time of insertion. Although, some might think that sorting while inserting will be done at higher cost of time complexity. But this is the magic of Tree-Set which provides the same implementation in O(log N) times.

How Tree-Set implements insertion in O(log N) ?

In Tree-Set, a self-balancing binary search tree is employed (Red-Black Tree). Therefore, sorting is achieved in the above time complexity while insertion.

Back to our problem, we will insert all our elements of array into a Tree-Set as below:

As of now, we have Tree-Set which contains our numbers in a sorted manner. Now next step would be try to find the longest consecutive sub-sequence in our sorted set.

For this, we will use two variable one would be count to store length of current sub-sequence and max to store the length of our longest consecutive sub-sequence. Now, the remaining task is to run a loop over the Tree-Set and then find out the maximum length of the consecutive sub-sequence.

Here, we have taken prev which will store the previous element and we have initialized it with the first element of the set. Now below are the steps we are following in the iteration:

1. To check if the number appearing is same as previous, then no need to update anything and we just continue the loop.
2. If current number (integer) is consecutive to previous number (prev), then we will increment the count by 1. Then, we will check that whether count value is greater than max, if yes then update max with count.
3. If current number (integer) is not consecutive to previous number (prev), then we will reset the count by 1.
4. Finally, we will update the value of prev with current number (integer).

Finally, longest consecutive sequence could be found in variable max, and could be returned.

Complexity of the above solution would be O(N), because insertion in Tree-Set would take O(log N) time but the loop for finding the longest consecutive sequence is taking O(N) time, because we are iterating over each element of the treeSet. Hence, in total it would be O(N).

For full source code visit Github repository.

Thanks for reading.