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.

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: