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.
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:
@programmingpraxis, I believe the usage of
sortin your2sum3function makes the functionO(n log n)as opposed toO(n).@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.
@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)toO(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).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.
I’m not sure of the exact complexity of my solution, but here it is anyway (in Julia as usual): https://pastebin.com/CwwPA0a6
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])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:
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]]