# 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. The generalized version, rSUM, asks the same question of r elements. 3SUM can be easily solved in $O(n^2)$ time, and matching $\Omega(n^{\lceil r/2 \rceil})$ 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 on average 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, achieving worst-case $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;
// Continue search for all triplet combinations summing to zero.
k = k + 1
l = l - 1
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 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.

## 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