|Is there an algorithm to solve the 3SUM problem faster than time?|
In computational complexity theory, the 3SUM problem asks if a given set of integers, each with absolute value bounded by some polynomial in , contains three elements that sum to zero. The generalized version, rSUM, asks the same question of r elements. 3SUM can be easily solved in time, and matching lower bounds are known in some specialized models of computation (Erickson 1999). Slightly faster randomized algorithms are known that exploit computational-model parallelism on a RAM and in the external-memory and cache-oblivious models (Baran, Demaine & Pǎtraşcu 2008). When the integers are in the range , 3SUM can be solved in time by representing the input set as a bit vector, computing the set of all pairwise sums as a discrete convolution using the Fast Fourier transform, and finally comparing this set to .
Suppose the input array is . 3SUM can be solved in time on average by inserting each number into a hash table, and then for each index and , checking whether the hash table contains the integer .
Alternatively, 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 time, as follows.
sort(S); for i=0 to n-3 do a = S[i]; start = i+1; end = n-1; while (start < end) do b = S[start]; c = S[end]; if (a+b+c == 0) then output a, b, c; // Continue search for all triplet combinations summing to zero. start = start + 1 end = end - 1 else if (a+b+c > 0) then end = end - 1; else start = start + 1; end end end
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.
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) in analysis of algorithms in computational geometry. By now there are a multitude of 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?
- Baran, Ilya; Demaine, Erik D.; Pătraşcu, Mihai (2008), Subquadratic algorithms for 3SUM, Algorithmica 50 (4): 584–596, doi:10.1007/s00453-007-9036-3.
- Demaine, Erik D.; Mitchell, Joseph S. B.; O'Rourke, Joseph (July 2005), Problem 11: 3SUM Hard Problems, The Open Problems Project.
- Erickson, Jeff (1999), Lower bounds for linear satisﬁability problems, Chicago Journal of Theoretical Computer Science (MIT Press) 1999.
- Gajentaan, Anka; Overmars, Mark H. (1995), On a class of O(n2) problems in computational geometry, Computational Geometry: Theory and Applications 5 (3): 165–185, doi:10.1016/0925-7721(95)00022-2.
- King, James (2004), A survey of 3SUM-hard problems.