[Java] Longest subsequence of consecutive numbers

Given an unsorted array of numbers, with duplicates allowed, find the length of the longest sequence of consecutive numbers.

An easy approach is to sort the input in O(N logN) time and then walk over it in O(N) time to find our answer. There are two problems here: (1) we need to sort and (2) if sort algorithm is not in place, it uses extra O(N) space.

If we view each number as the leftmost point in a sequence, we either have a number before that and therefore we are part of the longer sequence starting at that number or we do not have a number before it, which means we are the starting point a sequence.

We can search for all consecutive numbers starting from the current one in our input and keep going until we find a match.

By using a O(N) extra space for a set, we can lookup whether a number is in our input or not in constant time and also remove duplicates.

Then for each number in our input we execute this logic. 

From a given number we will either cover all other numbers (meaning the input contains an uninterrupted sequence from first to last element) or stop when we can't find a successor.
When we move on to the next element in the input, we will NOT repeat this process IF its predecessor is in the set, we therefore scan the array multiple times, but each time we only walk a portion of it.
The length of all these portions together is N, meaning we do at most 2N work and not N^2

Examples:

123

Our set contains 1,2,3
start at element 1, 0 (1-1) is not in the set, we start our scan and find that all elements up to 3 are in the set
The longest sequence starting at 1 is 3.
move to element 2, 1 (2-1) is in the set, we skip it
move to element 3, 2 (3-1) is in the set, we skip it
We reached end of array

321

Our set contains 1,2,3
start at element 3, 2 (3-1) is in the set, we skip it
move to element 2, 1 (2-1) is in the set, we skip it
move to element 1, 0 (1-1) is not in the set, we start our scan and find that all elements up to 3 are in the set
The longest sequence starting at 1 is 3.
We reached end of array

134

Our set contains 1,3,4
start at element 1, 0 (1-1) is not in the set, we start our scan and find that the next 2 (1+1) is missing. We stop
searching, the current longest subsequence is 1.
move to element 3, 2 (3-1) is in the set, we start our scan and find that all elements up to 4 are in the set
The longest sequence starting at 3 is 2.
move to element 4, 3 (4-1) is in the set, we skip it
We reached end of array

You can check my implementation of longestSequenceOfConsecutiveNumbers on my Gist along with some tests in LongestSequenceOfConsecutiveNumbersJTests.