3SUM

June 18, 2013

Today’s exercise is a classic problem of computer science: given an array of positive and negative integers, find three that sum to zero, or indicate that no such triple exists. This is similar to the subset sum problem, which we solved in a previous exercise, but simpler because of the limit to three items. A brute force solution that operates in O(n3) time uses three nested loops to select items from the array and test their sum, but an O(n2) solution exists. For instance, in the array [8, -25, 4, 10, -10, -7, 2, -3], the numbers -10, 2 and 8 sum to zero, as do the numbers -7, -3, and 10.

Your task is to write a program that solves the 3SUM problem in O(n2) time. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

7 Responses to “3SUM”

  1. […] today’s Programming Praxis exercise, our goal is to find all groups of three numbers in a given list that […]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2013/06/18/programming-praxis-3sum/ for a version with comments):

    import Data.List
    import qualified Data.IntSet as I
    
    sum3 :: [Int] -> [[Int]]
    sum3 xs = nub [sort [a,b,-a-b] | (a:bs) <- tails xs, b <- bs, I.member (-a-b) s]
              where s = I.fromList xs
    
  3. Jussi Piitulainen said

    Accepting (-1,2,-1) or (0,0,0) as a solution if -1 or 0 occurs in the bag more than once or twice, respectively. This produces all permutations, including duplicates if a solution contains duplicate elements. Python’s True and False appear to count as 1 and 0.

    from collections import Counter
    def threesums(bag):
        c = Counter(bag)
        for j, m in enumerate(bag):
            for k, w in enumerate(bag):
                if j == k: continue
                if c[-(m + w)] > (m == -(m + w)) + (w == -(m + w)):
                    yield m, w, -(m + w)
    
  4. […] Problem Description Given an array of positive and negative integers, find three that sum to zero. […]

  5. Stefan Jaax said

    Imho, the proposed solution using hash tables is NOT a valid solution.
    To see this, look at the following run on the list [10, -20] (which should return an empty list for all 3 versions of 3sum):

    http://codepad.org/Sqo8kiCx

  6. Jussi Piitulainen said

    Stefan, agreed. That’s precisely why I counted the occurrences in my solution:

    >>> tuple(threesums((10,-20)))
    ()
    >>> tuple(threesums((10,-20,10)))
    ((10, -20, 10), (10, 10, -20), (-20, 10, 10), (-20, 10, 10), (10, 10, -20), (10, -20, 10))
    

    (This is also a hash table solution.)

  7. Ronnie said

    A c++ implementation of the algorithm.

    #include
    #include
    void three_sum(std::vector input) {
    int lo = 1;
    int hi = input.size() – 1;
    for(int i = 0 ; i < input.size() – 1;) {
    if(lo < hi) {
    int sum = input[i] + input[hi] + input[lo];
    if(sum 0) {
    –hi;
    } else {
    printf(“%d + %d + %d = 0″,input[i],input[lo],input[hi]);
    ++i;
    lo = i+1;
    hi = input.size() – 1;
    }
    } else {
    ++i;
    lo = i+1;
    hi = input.size() – 1;
    }
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 635 other followers

%d bloggers like this: