The 3-sum problem asks if a given set $S$ of $n$ real numbers contains three elements that sum to zero.

I came to an interesting algorithm for solving it, but it created a different problem for me as you can see in the title. My algorithm works as follow:

Since we are searching for three elements that sum to $0$, then either one or two of them are negative, we can duplicate and multiply $S$ by $-1$ it will allow us to assume that there is just one negative element, however, the algorithm needs to run on both of the sets. To simplify it let's assume there is just one set $S$ and the below condition is met iff there are three elements that sum to $0$.

$$a + b + c = 0; a >= b >0; c < 0$$

I am ignoring the trivial case where one of the elements equal to $0$.

  • First I sort S for the cost of $n(\log{n})$
  • Now I start looking on all the negative elements $i_c$ from the largest one to the smallest one, and I am asking the question: What is the minimum sum of two items from the positive elements greater or equal to $-i_c$
    • in case I found equality the algorithm terminates with a positive result
    • in case I found some sum $u > -i_c$ then I can eliminate all the negative elements greater than $-u$

My approach for finding the sum is as follow.

  • First I realize that the upper bound for the sum is $-i_c$
  • I do a binary search to find the first element smaller than $-i_c$ let's call this element $i_a$. Let's say there are $k$ positive elements in this range.
  • Next, I do a binary search to find $i_b$. It's the first element greater or equal to $-i_c - i_b$. In case of a match the problem is solved, otherwise, I can reduce the upper bound to $-i_c - i_b$ and continue.

Using this approach, I will be testing at most $k/2$ items. In the worst case, $k$ will grow to be close to $n$. Also in the worst case, I will eliminate the negative elements one by one.

In the best case, I will find a solution while $k$ is redundant in comparison to $n$. The algorithm can also be improved by using selection sort to only look at the range of the inspected elements. It means that in the best case scenario this algorithm operates in linear time.

Ok so let me repeat the question now. Can you find a sub-linear algorithm for finding a min-sum greater then $x$ of a pair of elements in a sorted set of real numbers, where $x$ is some real number?


Your Answer

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

Browse other questions tagged or ask your own question.