From Wikipedia, the free encyclopedia
Jump to: navigation, search
List of unsolved problems in computer science
Is there an algorithm to solve the 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.

Quadratic algorithm[edit]

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]

 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;
          start = start + 1;

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 xX, yY?[2]


  1. ^ Visibility Graphs and 3-Sum by Michael Hoffmann
  2. ^ Demaine, Erik; Erickson, Jeff; O'Rourke, Joseph (20 August 2006). "Problem 41: Sorting X + Y (Pairwise Sums)". The Open Problems Project. Retrieved 23 September 2014. 


See also[edit]