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.