|Is there an algorithm to solve 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 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, again achieving time, as follows.
sort(S); for i=0 to n-3 do a = S[i]; k = i+1; l = n-1; while (k<l) do b = S[k]; c = S[l]; if (a+b+c == 0) then output a, b, c; exit; else if (a+b+c > 0) then l = l - 1; else k = k + 1; end end end
The following example shows this algorithm's execution on a small sorted array. Current values of a are shown in bold, 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 directions of the points 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 a or b, 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.
- Visibility Graphs and 3-Sum by Michael Hoffmann
- 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.