3SUM

June 18, 2013

We modify the problem statement to return all matching triplets, rather than just an arbitrary one of them. Let’s begin with the obvious brute-force algorithm:

(define (3sum-brute xs)
  (define (x n) (vector-ref xs n))
  (let ((len (vector-length xs)))
  (list-of (sort < (list (x i) (x j) (x k)))
    (i range len)
    (j range (+ i 1) len)
  (k range (+ j 1) len)
  (zero? (+ (x i) (x j) (x k))))))

> (3sum-brute '#(8 -25 4 10 -10 -7 2 -3))
((8 -10 2) (10 -7 -3))

We sort the individual triplets just to make them look nice.

There are two ways to improve that, one involving searching and the other involving sorting (isn’t it odd how often that choice arises?). The searching solution enters each array element in a hash table then chooses two items using two nested loops and searches the hash table for the negative of the sum of the two items; we use our new set datatype instead of a hash table, because we don’t need to associate a value with a key:

(define (3sum-search xs)
  (define (x n) (vector-ref xs n))
  (let ((s (make-set 97)) (len (vector-length xs)))
    (do ((i 0 (+ i 1))) ((= i len))
      (s 'adjoin (x i)))
    (list-of (sort < (list (x i) (x j) k))
      (i range len)
      (j range (+ i 1) len)
      (k is (- (+ (x i) (x j))))
      (s 'member? k))))

The output of 3sum-search is three times as long as it should be, since each triple appears with k in each of the three positions. We take a two-pronged approach to the problem; first, the triples are individually sorted (that’s the real reason we sorted them in the brute-force solution), then a prune function uses a set to keep only one copy of each triplet:

(define (prune xs)
  (let ((s (make-set 97)))
    (do ((xs xs (cdr xs))) ((null? xs))
      (s 'adjoin (car xs)))
    (s 'enlist)))

> (prune (3sum-search '#(8 -25 4 10 -10 -7 2 -3)))
((-7 -3 10) (-10 2 8))

The sorting solution first sorts the input array, then tests each item in the array searching for a zero triple in a manner reminiscent of binary search:

(define (3sum-sort xs)
  (vector-sort! xs cmp)
  (let ((len (vector-length xs)) (zs (list)))
    (define (x n) (vector-ref xs n))
    (do ((i 0 (+ i 1))) ((= i (- len 2)))
      (let loop ((lo (+ i 1)) (hi (- len 1)))
        (when (< lo hi)
          (let ((s (+ (x i) (x lo) (x hi))))
            (cond ((negative? s) (loop (+ lo 1) hi))
                  ((positive? s) (loop lo (- hi 1)))
                  (else (set! zs (cons (sort < (list (x i) (x lo) (x hi))) zs))))))))
    zs))

> (3sum-sort '#(8 -25 4 10 -10 -7 2 -3))
((-7 -3 10) (-10 2 8))

We used list comprehensions and the Bentley-McIlroy vector sort from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/zW0EmC9m.

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 630 other followers

%d bloggers like this: