## 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.

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

Output:

@programmingpraxis, I believe the usage of

`sort`

in your`2sum3`

function makes the function`O(n log n)`

as opposed to`O(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

outputis sorted as opposed to theinput), 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).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.

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.

Output: