# Two Sum Problem

My solution to this classic interview question.

You are given a finite list of integers (as a 1-dimensional array), and a target integer `a`

. Write an algorithm to determine if any two integers in the list sum to `a`

. The naive solution is to take the first integer in the list and iterate over the remaining integers, checking to see if they sum to `a`

. This has `O(n^2)`

run time where `n`

is the length of the list, because for each integer `x`

we need to check it against the other `n-1`

integers, so worst case we perform `n(n-1)`

checks which is `O(n^2)`

.

It turns out there is a solution which runs in `O(n)`

time. This employs the following trick: take the first integer in the list, call it `x_1`

, and store it in a hashtable. Next consider the second element `x_2`

and compute `a - x_2`

. Now check our hashtable to see if `a - x_2`

already exists. If it does then we’ve found a solution: if `a - x_2 = x_1`

then `a = x_1 + x_2`

. If it doesn’t exist then add `x_2`

to the hashtable. Next consider `x_3`

and compute `a - x_3`

. Now check our hashtable to see if this `a - x_3`

exists. If it does, say `a - x_3 = x_t`

for some `t`

, then `a = x_3 + x_t`

so we’ve found a solution. If it doesn’t exist then add `x_3`

to the hashtable. Continue in this fashion until either a solution is found or we’ve reach the end of the list and no solution exists.

Why is this `O(n)`

? Well for each integer `x`

in the list we perform a lookup in the hashtable which, given the properties of hashtables, is an `O(1)`

operation. Since we only enumerate the list once, and perform `O(1)`

operations at each step, our run time is therefore `O(n)`

.

One important factor to consider here is that although the second solution runs in `O(n)`

time it does use more memory, which scales like `O(n)`

, because in the worst case we store `n - 1`

elements in the hashtable. On the other hand the naive method does not require additional memory as the length of the list increases, so its memory usage scales like `O(1)`

. Thus there is a trade off between speed and memory usage. The best algorithm for the task will depend on whether you are interested in speed or minimizing resources.

It’s a good exercise to code up both examples. This page provides examples in a number of different programming languages: https://coderbyte.com/algorithm/two-sum-problem.