2SUM

March 10, 2020

We begin by making a list of random integers:

(define xs
  (shuffle
    (unique =
      (sort <
        (map (lambda (n) (- (random 50) 25))
             (range 60))))))
> xs
(12 6 -21 17 -17 10 -5 -18 22 -20 16 13 -19 0 -16 -6 -3 -23
 -2 7 19 14 -1 -12 -10 23 -24 -14 -15 -7 -22 3 -13 4 -9 24)

Our O(n²) algorithm is a simple list comprehension:

(define (2sum1 t xs)
  (sort (lambda (a b) (< (car a) (car b)))
    (list-of (list a b)
      (a in xs)
      (b in xs)
      (< a b)
      (= (+ a b) t))))

We sort the pairs and sort the output because it seems sensible:

> (2sum1 19 xs)
((-5 24) (-3 22) (0 19) (3 16) (6 13) (7 12))

We report there are no pairs by returning the null list:

> (2sum1 44 xs)
()

Our O(n log n) algorithm sorts the list, then uses two pointers that approach each other from opposite ends; when the sum of the elements at the two pointers exceeds the target, decrement the high pointer, when the sum of the elements at the two pointers is less than the target, increment the low pointer, with the sum of the elements at the two pointers equals the target, accumulate a new solution, and when the two pointers meet, report the result:

(define (2sum2 t xs)
  (let ((xv (list->vector (sort < xs))))
    (let loop ((lo 0) (hi (- (length xs) 1)) (result (list)))
      (let* ((a (vector-ref xv lo)) (b (vector-ref xv hi)) (s (+ a b)))
        (cond ((= lo hi) (sort (lambda (a b) (< (car a) (car b))) result))
              ((< s t) (loop (+ lo 1) hi result))
              ((< t s) (loop lo (- hi 1) result))
              (else (loop (+ lo 1) (- hi 1)
                          (cons (list a b) result))))))))
> (2sum2 19 xs)
((-5 24) (-3 22) (0 19) (3 16) (6 13) (7 12))

Our O(n) algorithm first enters each input integer into a hash table, then tests each difference to the target:

(define (2sum3 t xs)
  (let ((ht (make-eq-hashtable)))
    (do ((xs xs (cdr xs))) ((null? xs))
      (hashtable-set! ht (car xs) (car xs)))
    (let loop ((xs xs) (result (list)))
      (if (null? xs) (sort (lambda (a b) (< (car a) (car b))) result)
        (let ((a (car xs)) (b (- t (car xs))))
          (if (and (< a b) (hashtable-contains? ht b))
              (loop (cdr xs) (cons (list a b) result))
              (loop (cdr xs) result)))))))
> (2sum3 19 xs)
((-5 24) (-3 22) (0 19) (3 16) (6 13) (7 12))

This program fails on all three Scheme interpreters at ideone, though it works fine on Chez. Maybe someday the Scheme community will get its act together.

Pages: 1 2

9 Responses to “2SUM”

  1. Daniel said

    Here’s a solution in Python, where I’ve assumed the input list of integers does not contain duplicates.

    from bisect import bisect_left
    
    def twosum1(l, t):
        return [(x, y) for i, x in enumerate(l) for y in l[i + 1:] if x + y == t]
    
    def twosum2(l, t):
        l = sorted(l)
        idxs = (bisect_left(l, t - x, lo=idx + 1) for idx, x in enumerate(l))
        return [(x, l[idx]) for x, idx in zip(l, idxs) if idx < len(l) and x + l[idx] == t]
    
    def twosum3(l, t):
        s = set(l)
        return [(x, t - x) for x in s if t - x in s and x < t - x]
    
    l = [-2, 10, 2, -3, 4, 0, 3, 9, 8, 1, -4, 6, 5, 7]
    t = 6
    print(twosum1(l, t))
    print(twosum2(l, t))
    print(twosum3(l, t))
    

    Output:

    [(-2, 8), (10, -4), (2, 4), (-3, 9), (0, 6), (1, 5)]
    [(-4, 10), (-3, 9), (-2, 8), (0, 6), (1, 5), (2, 4)]
    [(0, 6), (1, 5), (2, 4), (-4, 10), (-3, 9), (-2, 8)]
    
  2. Daniel said

    @programmingpraxis, I believe the usage of sort in your 2sum3 function makes the function O(n log n) as opposed to O(n).

  3. programmingpraxis said

    @Daniel: The sort is on the output, not the input, so it won’t contribute appreciably to the time complexity of the function. You could omit the sort and get the same output, but the pairs would be in random order.

  4. Daniel said

    @programmingpraxis. Thanks! That matches how I interpreted your function (that the output is sorted as opposed to the input), but my thought was that doing so changes the time complexity from O(n) to O(n log n) since the output size can grow with the input size (e.g., it’s not bounded by a constant, and can be up to half the size of the input).

  5. Greg said

    I don’t think your O(n) solution is correct unless you know the range of input data. For an arbitrary range, a hash-map always has a chance of hash collision. In the worst case it can collide with all other hashes.

    In your example, you could use a hash-map with 50 slots and an identity hash (mod 50). But if my input ranged over all integers, this solution simply isn’t feasible except purely in theory.

  6. Zack said

    I’m not sure of the exact complexity of my solution, but here it is anyway (in Julia as usual): https://pastebin.com/CwwPA0a6

  7. Paul said

    In Python 3.8 using the Walrus operator. It is assumed there are no duplicates.

    def twosum(arr, target):
        S = set(arr)
        return sorted([(a, b) for a in arr if (b:=target-a) in S and a < b])
    
  8. Daniel said

    Here’s a solution in Python that supports duplicates in the input. The output is a list that includes pairs and their corresponding counts, as duplicates in the input permits duplicates in the output.

    from collections import Counter
    
    def twosum4(l, t):
        output = []
        c = Counter(l)
        for x, count in c.items():
            y = t - x
            if x < y and y in c:
                output.append(((x, y), count * c[y]))
            elif x == y and c[x] > 1:
                output.append(((x, y), (count * (count - 1) // 2)))
        return output
    
    l = [-2, -8, 10, 2, 3, -3, 4, 0, 3, 9, 8, 1, -4, 6, 5, 5, 7, 3]
    t = 6
    print(twosum4(l, t))
    

    Output:

    [((-2, 8), 1), ((2, 4), 1), ((3, 3), 3), ((-3, 9), 1), ((0, 6), 1), ((1, 5), 2), ((-4, 10), 1)]
    
  9. Steve said
    Klong version (Not sure of time required)
    
             :"Splits list into 3 sublists and returns them:  Members of list less than half the number, members equal to half the number and members greater than half the number"
             f1::{[eql less lst more n2];more::less::eql::[];lst::x;n2::y%2;{:[x<n2;{less::less,x}(x):|x>n2;{more::more,x}(x);{eql::eql,x}(x)]}'lst;(,less),(,more),(,eql)}
    
             :"Compares 1st and 3rd lists for matching sum and returns those sums with pair (if any) from list 2"
             f2::{[acc eql less lst more n];lst::x;n::y;lst::f1(lst;n);less::lst@0;more::lst@1;eql::lst@2;acc::,/?(,{(x@0),less@x@1}'lst@&{1<#x}'lst::{x,less?n-x}'more);?:[1<#eql;acc,(,2#eql);acc]}
    
            f2([-2 -8 10 2 3 -3 4 0 3 9 8 1 -4 6 5 5 7 3];6)
    [[10 -4] [4 2] [9 -3] [8 -2] [6 0] [5 1] [3 3]]
    
    

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: