The following is a common problem with a twist -
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in
O(n)complexity.
Direct Solution
The most direct solution is to sort the array and then traverse the sorted array while keeping track of the subsequences encountered, along with their respective lengths. The caveat to the problem however, is that this solution run in O(n) complexity. Sorting a list puts the direct solution over that required complexity at O(n log n)
Alternative Solution
Hash Set lookup
The problem does not constrain on memory complexity. We could therefore store all the elements in a Set. This would only cost O(1) in time complexity for storing and retrieving elements
First Element ?
We can now traverse the original list, and check if the current element is the first element in a subsequence. This can be achieved by looking for the previous element in the set that we created
Subsequences
With the first element in hand, it is now possible to look for all subsequent elements in that subsequence by checking the set for the next element until we no longer have a subsequence. A counter keeps track of our subsequence length. This counter can be compared to a global max and swapped if greater.
Once we have traversed the entire list, the max count is our solution. We do have to make 2 passes over our list however, this would still amount to constant time complexity
