1
$\begingroup$

Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D.

For example, given D = 5, with the set of numbers 1, 5, 10, 6, 7, 8, 15, 11 the longest sequence would be 5, 10, 15

I have tried using sets to solve this but I can't find a solution faster than $O(n^2)$. For example, I have tried adding all items in the array to a TreeSet. This automatically orders the elements, after which I brute force check all the possible sequences. Am I on the right lines or is there a better approach?

Improve this question
$\endgroup$
6
  • $\begingroup$ The worst-case amortized running time per operation is $\Theta(\alpha(n))$. Worse, the find operation doesn't do what you think it does. $\endgroup$
    – Yuval Filmus
    Commented May 13, 2019 at 20:58
  • $\begingroup$ Using a hashtable you can solve this in expected $O(n)$ time. Insert everything into the hashtable. For each $x$ such that $x-D$ is not in the list, check the length of the longest arithmetic progression starting at $x$. Without a hashtable, you can run this algorithm in $O(n\log n)$ after sorting the list. If the list is already sorted, then by being smarter, you can solve this in $O(n)$: using two pointers, add edges from $x$ to $x+D$, then run the second half of the hashtable algorithm. $\endgroup$
    – Yuval Filmus
    Commented May 13, 2019 at 21:04
  • $\begingroup$ Are all numbers integers? Is memory usage a big concern? $\endgroup$
    – John L.
    Commented May 13, 2019 at 22:26
  • $\begingroup$ @Apass.Jack Yes, positive integers. No. $\endgroup$
    – EightPinkArrows
    Commented May 13, 2019 at 23:13
  • $\begingroup$ @YuvalFilmus I completely misread what the find method does, my mistake. Could you please explain your hash table solution again? I'm confused as to how the time complexity is O(n). Also how do you handle gaps in sequences? I only figured out a O(n log n) solution using a hash table. $\endgroup$
    – EightPinkArrows
    Commented May 14, 2019 at 1:01

1 Answer 1

Reset to default
3
$\begingroup$

Using a hashtable, you can solve this in $O(n)$ expected time, as follows:

  • Fill a hashtable $H$ with the given numbers.
  • Go over all numbers in the list. For each number $x$, if $x-D \notin H$:
    • Go over the numbers $x + D, x + 2D, x + 3D, \ldots$ until you find a number not in $H$.

The running time of the first step is $O(n)$. As for the second step, the potentially expensive step is the sub-step. However, in this sub-step we go over each element in the list at most once (we check $y$ only for $x = y-aD$, where $a$ is the maximal integer such that $y-aD \in H$), and so the second step takes $O(n)$ time.

Without using a hashtable but assuming that the list is sorted, we can solve this in $O(n)$ time as follows:

  • Go over all numbers in the list. For each number $x$, add an edge to $x+D$ if $x+D$ is in the list.
  • Go over all numbers again. For each number $x$, if there is no edge pointing at $x$, follows the path starting at $x$ and calculate its length.

Using two pointers, we can implement the first step in $O(n)$. (The first pointer points at $x$, the other one is looking for $x+D$.) The second step takes $O(n)$ time for the same reason as in the hashtable algorithm.

Since it takes $O(n\log n)$ time to sort the list, this solution runs in time $O(n\log n)$. Using the fast $O(n\log\log n)$ integer sorting algorithm, we obtain a solution running in time $O(n\log\log n)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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