Given an array of positive and negative numbers(distinct), How do we find the length of the longest consecutive subset?
For example consider the below array
{3, 6, 1, 2, 5, 7, 8}
It contains {5,6,7,8} as the longest consecutive subset. So the answer is 4.
Similarly for {2, 4, 6, 8}, the answer is 1 as there are no consecutive numbers.
Lets discuss two algorithms to solve this problem.
Method based on sorting:
We sort all the elements in ascending order. This would take O(n log n) time. Then we compare the adjacent elements to check if they are consecutive. If any two elements are not consecutive, we break the sequence and update the maximum length. getMaxConsecutiveSubset1() method in the code implements this algorithm. The overall complexity of this algorithm is
O(n log n).
Method based on Hash map:
Let us take a Hash map which stores the all the elements with a flag for each which indicates if it is visited or not visited.
- Initially we store all the elements to the map with visited flag as false.
- For each element do the following
- If it is not visited earlier
- Mark the element as visited
- Initiate a sequence of length 1
- Try to extend this sequence backward by marking the elements visited
- Try to extend this sequence forward by marking the elements visited
- Update the maximum sequence length
Here is the Java code which implements the above algorithm. It runs in O(n) time and O(n) space.