Best Sum of Three Elements in a Sequence

Question

I encountered the following problem:

Given an integer sequence $\left(s_1,s_2,\dots,s_n\right)$ and an integer $l$, find $$\min\left|s_i+s_j+s_k-l\right|,$$ where $i\neq j\neq k\neq i$, and return $s_i+s_j+s_k$.

For example: given $\left(-1,2,1,-4\right)$ and $l=1$, following the above criteria, we obtain $-1+2+1=2$.

I wrote a program that considers all $n\choose3$ possibilities; it runs in $O(n^3)$ time.

Is there a faster approach? If so, could you hint me toward it?

Answer 1

Here's another $O(n^2\log n)$ algorithm, similar to Ross Millikan's but slightly different. Start by sorting the $s_i$'s into increasing order, i.e., assume $s_1\le s_2\le\cdots\le s_n$. This can be done in $O(n\log n)$ steps, so we can assume the $s_i$'s came this way. Given such an ordered sequence, and given any number $S$, straightforward "bisection" will locate an integer $k$ such that $s_k\le S\le s_{k+1}$ (allowing for $s_0=-\infty$ and $s_{n+1}=\infty$) in $O(\log n)$ steps. The algorithm now runs through the $O(n^2)$ pairs $(s_i,s_j)$, lets $S=l-s_i-s_j$, finds the corresponding integer $k$ for each value of $S$, and keeps track of whether a new minimum is obtained. To be somewhat more precise, use the replacement formula

$$M\to\min\{M,(S-s_{k-2}),(S-s_{k-1}),(S-s_k),(s_{k+1}-S),(s_{k+2}-S),(s_{k+3}-S)\}$$

but knocking out any of the terms with a subscript equal to $i$ or $j$. (This last wrinkle is to meet the stipulation $i\not=j\not=k\not=i$.)

Added later: It occurs to me that one might as well assume that $l=0$ in describing an algorithm, by replacing each $s_i$ with $3s_i-l$. This means, in effect, that the complexity problem boils down to looking for an algorithm that takes two sequences

$$0\le p_1\le p_2\le \cdots\le p_n\le\infty \quad {and}\quad 0\le q_1\le q_2\le\cdots\le q_n\le\infty$$

and seeks to minimize $|p_i+p_j-q_k|$ with $i\not=j$. (I'm omitting various details of how the OP's problem connects to this one, but I hope the general nature of the connection is clear. What's unclear, to me at least, is whether this throws any light on the original problem. Still, I thought it worth mentioning.)

Answer 2

Since $k$ is given, the value of $s_k - k$ is also known, so you only need to look through all possible $ij$ pairs; that's $O(n^2)$.

Answer 3

You can do $O(n^2 \log n)$. Let us work on the same problem without $s_k$, so we are minimizing $|s_i+s_j-l|$ and show an $O(n \log n)$ algorithm. Then you can just loop $k$ from $1$ to $n$ to get $O(n^2 \log n)$. Sort the $s$'s into an array $t_1,t_2\dots t_n$ with $t_1 \lt t_2 \lt \dots t_n$ Now compute $t_1+t_n-l$ If it is positive, you may improve things by replacing $t_n$ by $t_{n-1}$. If it is negative, you may improve things by replacing $t_1$ by $t_2$. Keep stepping in until you meet in the middle and report the best result you found.