Member-only story
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:
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:
