3SUM

From Wikipedia, the free encyclopedia
Jump to: navigation, search
List of unsolved problems in computer science
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^{r/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.

Quadratic algorithm[edit]

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;
          // 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[edit]

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[edit]

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

References[edit]

See also[edit]