# 3SUM

 Is there an algorithm to solve 3SUM problem faster than $O(n^2)$ time?

In computational complexity theory, the 3SUM problem asks if a given set of $n$ integers, each with absolute value bounded by some polynomial in $n$, contains three elements that sum to zero. This problem can be easily solved in $O(n^2)$ time, and matching $\Omega(n^2)$ 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 $[-u, \dots, u]$, 3SUM can be solved in $O(n + u\log u)$ time by representing the input set $S$ as a bit vector, computing the set $S+S$ of all pairwise sums as a discrete convolution using the Fast Fourier transform, and finally comparing this set to $-S$.

## Contents

Suppose the input array is $S[0..n-1]$. 3SUM can be solved in $O(n^2)$ time by inserting each number $S[i]$ into a hash table, and then for each index $i$ and $j$, checking whether the hash table contains the integer $-S[i]-S[j]$.

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 $O(n^2)$ time, as follows.[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
```

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)
```

## 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) in analysis of algorithms in computational geometry. By now there are a multitude of problems that fall into this category.

## Notes

1. ^ Visibility Graphs and 3-Sum by Michael Hoffmann