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