19
$\begingroup$

This is inspired by an interview question.

We are given an array of integers $a_1, \dots, a_n$ and have to determine if there are distinct $i \lt j \lt k$ such that

  • $a_k - a_j = a_j - a_i$
  • $k - j = j - i$

i.e, the sequences $\{a_i, a_j, a_k\}$ and $\{i,j,k\}$ are both in arithmetic progression.

There is an easy $O(n^2)$ algorithm for this, but finding a sub-quadratic algorithm seems elusive.

Is this a known problem? Can we prove 3SUM-hardness of this? (or maybe provide a sub-quadratic algorithm?)

If you like, you can assume $0 \lt a_1 \lt a_2 \lt ... \lt a_n$ and that $a_{r+1} - a_{r} \le K$ for some known constant $K > 2$. (In the interview problem, $K = 9$).

$\endgroup$
12
$\begingroup$

This is an open problem.

Possibly some weak form of 3SUM-hardness could be proved by adapting a result from Mihai Pătrașcu's STOC 2010 paper "Towards Polynomial Lower Bounds for Dynamic Problems". First, let me define a sequence of closely related problems. The input to each problem is a sorted array $A[1..n]$ of distinct integers.

  • 3SUM: Are there distinct indices $i,j,k$ such that $A[i] + A[j] = A[k]$?

  • Convolution3SUM: Are there indices $i<j$ such that $A[i] + A[j] = A[i+j]$?

  • Average: Are there distinct indices $i,j,k$ such that $A[i] + A[j] = 2 A[k]$?

  • ConvolutionAverage: Are there indices $i<j$ such that $A[i] + A[j] = 2A[(i+j)/2]$? (This is the problem you're asking about.)

In my PhD thesis, I proved that all four of these problems require $\Omega(n^2)$ time in a decision-tree model of computation that allows only queries of the form "Is $\alpha A[i] + \beta A[j] + \gamma A[k] + \delta$ positive, negative, or zero?", where $\alpha,\beta,\gamma,\delta$ are real numbers (that don't depend on the input). In particular, any 3SUM algorithm in this model must ask the question "Is $A[i] + A[j]$ bigger, smaller, or equal to $A[k]$?" at least $\Omega(n^2)$ times. That lower bound doesn't rule out subquadratic algorithms in a more general model of computation — indeed, it is possible to shave off some log factors in various integer RAM models. But nobody knows what sort of more general model would help more significantly.

Using a careful hashing reduction, Pǎtrașcu proved that if 3SUM requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then Convolution3SUM requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time. Thus, it's reasonable to say that Convolution3SUM is "weakly 3SUM-hard". For example, if Convolution3SUM can be solved in $O(n^{1.8})$ time, then 3SUM can be solved in $O(n^{1.9})$ time.

I haven't ground through the details, but I'd bet that a parallel argument implies that if Average requires $\Omega(n^2/f(n))$ expected time, for any function $f$, then ConvolutionAverage requires $\Omega(n^2/f^2(n\cdot f(n)))$ expected time. In other words, ConvolutionAverage is "weakly Average-hard".

Unfortunately, it is not known whether Average is (even weakly) 3SUM-hard! I suspect that Average is actually not 3SUM-hard, if only because the $\Omega(n^2)$ lower bound for Average is considerably harder to prove than the $\Omega(n^2)$ lower bound for 3SUM.


You also ask about the special case where adjacent array elements differ by less than some fixed integer $K$. For 3SUM and Average, this variant can be solved in $O(n \log n)$ time using Fast Fourier transforms as follows. (This observation is due to Raimund Seidel.)

Build a bit vector $B[0..Kn]$, where $B[i]=1$ if and only if the integer $A[1]+i$ appears in the input array $A$. Compute the convolution of $B$ with itself in $O(Kn\log Kn) = O(n\log n)$ time using FFTs. The resulting array has a non-zero value in the $j$th position if and only if some pair of elements in $A$ sum to $2A[1] + j$. Thus, we can extract a sorted list of sums $A[i]+A[j]$ from the convolution in $O(n)$ time. From here, it's easy to solve Average or 3SUM in $O(n)$ time.

But I don't know a similar trick for Convolution3SUM or ConvolutionAverage!

$\endgroup$

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.