# Longest AP that can be formed (with difference 1) in an unsorted array of integers

By integers, I mean a whole number.

Example:

Input : 2, 4, 7, 9, 3, 1, 11

Output: 1,2,3,4 forms an AP (of difference 1) with length 4.


An obvious solution is to sort the array with a comparison based algorithm O(nlogn) and then do a second scan through the unsorted array to find the longest sequence.

Can we have a better time complexity (at the expense of addition space)?

Go over all nodes, putting the unique nodes in a hashtable, and constructing a new array only with the unique values. Now go over the new array and upgrade it to a graph $G = (V,E)$ in which $V$ are the unique values and the edges connect $i$ to $i+1$. Go over the graph, and whenever you see a vertex with no incoming edge, follow the unique path emanating from it and count its length. The answer is the maximal length of such a path.
This solution uses a hashtable to efficiently construct the graph. This suggests that you might not be able to do better than $n\log n$ if you are only allowed to use comparisons. One way to prove it would be by reduction from element uniqueness, which is known to require $n\log n$ comparisons.