2SUM
March 10, 2020
We’ve done this in a previous exercise, but it’s a common problem both as an interview question and in programming classes, and I’ve seen in it several times in the last week, so now is a good time to do it again:
Given a list of integers and a target integer, find all the pairs of integers in the list that sum to the target integer, or report that there are no such pairs.
Your task is to write a program to find pairs of integers that sum to a target; you should write three programs, with time complexities of O(n²), O(n log n), and O(n). When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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]]