Longest consecutive elements sequence

For example, in {5, 7, 3, 4, 9, 10, 1, 6, 15, 1, 3, 12, 2, 11} longest sequence is {1, 2, 3, 4, 5,6}.

The first thing that comes into our mind is to sort given array in O(n log n ) and look for longest consecutive elements sequence. Can we do it in Linear time?

The next solution would be using bit vector indexed by numbers from original array. It may not be justified due to incomparable solution space and original array size (although time complexity is O(n)).

Lets see how to solve this problem in O( n ) time complexity with constant space assuming the hashtable has O(1) time complexity and constant space complexity.

By Knowing range boundaries we can definitely say what numbers are in there (for example, [1..3] contains 1, 2, 3). O(1) time complexity for range manipulation operations with O(1) space complexity for each range are the things we are looking for. We can do this using two hash tables:

• ‘low’ with range start numbers as keys and range end numbers as values
• ‘high’ with range end numbers as keys and range start numbers as values

For example, for a range [x..y] the tables will hold low[x] = y and high[y] = x. The algorithm looks the following:

• Scan original array and for each element:
  • If it already belongs to any range skip it
  • Otherwise create unit size range [i..i]
  • If there is a range next to the right [i+1.. y] merge with it to produce [i..y] range
  • If there is a range next to the left [x..i-1] merge with it as well (either [i..i] or merged [i..y] will be merged with [x..i-1])
• Scan through created ranges to find out the longest