| Is there an algorithm to solve 3SUM problem faster than O(n2) time? |
In computational complexity theory, 3SUM is the following computational problem conjectured to require roughly quadratic time:
There is a simple algorithm to solve 3SUM in O(n2) time. This is the fastest algorithm known in models that do not decompose the integers into bits, but matching lower bounds are only known in very specialized models of computation. 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 [−u ... u], 3SUM can be solved in time O(n + u lg u) by representing S as a bit vector and performing a discrete convolution using FFT.
Contents |
Assume we have as input array S with elements S[0]..S[n-1]. Then the following algorithm will solve 3SUM problem in quadratic time.[1]
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
Here is example how the above algorithm will find the result for some input (after it is sorted). 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)
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.