In computational complexity theory, the 3SUM problem asks if a given set of
Contents
- Quadratic algorithm
- Non zero sum
- 3 different arrays
- Convolution sum
- Reduction from Conv3SUM to 3SUM
- Reduction from 3SUM to Conv3SUM
- 3SUM hardness
- References
It was widely conjectured that any deterministic algorithm for the 3SUM requires
When the elements are integers in the range
Quadratic algorithm
Suppose the input array is
It is also possible to solve the problem in the same time in a comparison-based model of computing or real RAM, for which hashing is not allowed. The algorithm below first sorts the input array and then tests all possible pairs in a careful order that avoids the need to binary search for the pairs in the sorted list, achieving worst-case
The following example shows this algorithm's execution on a small sorted array. Current values of a are shown in green, values of b and c are shown in red.
-25 -10 -7 -3 2 4 8 10 (a+b+c==-25) -25 -10 -7 -3 2 4 8 10 (a+b+c==-22) . . . -25 -10 -7 -3 2 4 8 10 (a+b+c==-7) -25 -10 -7 -3 2 4 8 10 (a+b+c==-7) -25 -10 -7 -3 2 4 8 10 (a+b+c==-3) -25 -10 -7 -3 2 4 8 10 (a+b+c==2) -25 -10 -7 -3 2 4 8 10 (a+b+c==0)The correctness of the algorithm can be seen as follows. Suppose we have a solution a + b + c = 0. Since the pointers only move in one direction, we can run the algorithm until the leftmost pointer points to a. Run the algorithm until either one of the remaining pointers points to b or c, whichever occurs first. Then the algorithm will run until the last pointer points to the remaining term, giving the affirmative solution.
Non-zero sum
Instead of looking for numbers whose sum is 0, it is possible to look for numbers whose sum is any constant C in the following way:
3 different arrays
Instead of searching for the 3 numbers in a single array, we can search for them in 3 different arrays. I.e., given three arrays X, Y and Z, find three numbers a∈X, b∈Y, c∈Z, such that
Given a solver for 3SUM×1, the 3SUM×3 problem can be solved in the following way (assuming all elements are integers):
By the way we transformed the arrays, it is guaranteed that a∈X, b∈Y, c∈Z.
Convolution sum
Instead of looking for arbitrary elements of the array such that:
the convolution 3sum problem (Conv3SUM) looks for elements in specific locations:
Reduction from Conv3SUM to 3SUM
Given a solver for 3SUM, the Conv3SUM problem can be solved in the following way.
Correctness proof:
Reduction from 3SUM to Conv3SUM
Given a solver for Conv3SUM, the 3SUM problem can be solved in the following way.
The reduction uses a hash function. As a first approximation, assume that we have a linear hash function, i.e. a function h such that:
Suppose that all elements are integers in the range: 0...N-1, and that the function h maps each element to an element in the smaller range of indices: 0...n-1. Create a new array T and send each element of S to its hash value in T, i.e., for every x in S:
Initially, suppose that the mappings are unique (i.e. each cell in T accepts only a single element from S). Solve Conv3SUM on T. Now:
This idealized solution doesn't work, because any hash function might map several distinct elements of S to the same cell of T. The trick is to create an array T* by selecting a single random element from each cell of T, and run Conv3SUM on T*. If a solution is found, then it is a correct solution for 3SUM on S. If no solution is found, then create a different random T* and try again. Suppose there are at most R elements in each cell of T. Then the probability of finding a solution (if a solution exists) is the probability that the random selection will select the correct element from each cell, which is
Unfortunately, we do not have linear perfect hashing, so we have to use an almost linear hash function, i.e. a function h such that:
This requires to duplicate the elements of S when copying them into T, i.e., put every element
3SUM-hardness
A problem is called 3SUM-hard if solving it in subquadratic time implies a subquadratic-time algorithm for 3SUM. The concept of 3SUM-hardness was introduced by Gajentaan & Overmars (1995). They proved that a large class of problems in computational geometry are 3SUM-hard, including the following ones. (The authors acknowledge that many of these problems are contributed by other researchers.)
By now there are a multitude of other problems that fall into this category. An example is the decision version of X + Y sorting: given sets of numbers X and Y of n elements each, are there n² distinct x + y for x ∈ X, y ∈ Y?