1
$\begingroup$

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)?

$\endgroup$
1
$\begingroup$

If you're allowed to use hash tables, you can get a linear time algorithm.

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.

$\endgroup$
  • $\begingroup$ What you are doing is a HashSort essentially. $\endgroup$ – rents Jun 17 '17 at 13:38
  • $\begingroup$ Possibly, I've never heard of HashSort. $\endgroup$ – Yuval Filmus Jun 17 '17 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.