Sum of Two Elements

Problem

Given a target number and integer array, find all unique pairs of elements whose summation is equal to the target number.

Solution

Let’s say that we have an array with the following integers:

And let’s say that the target is as follows:

The first solution that comes to mind is to hold onto the first number in the array (which is 5 in this case), and then check the rest of the array for 3’s (since 8 – 5 = 3). Let’s quickly work through this first solution.

First Solution

Let’s design an algorithm that holds on to each element in the array, and then checks to see if there is another element in the array that will sum to the target.

Here is the pseudocode for the algorithm:

This algorithm will successfully return all of the number pairs that add up to the target number. However, it is not a very efficient algorithm. For each element we will be iterating through the rest of the array which results in an O(n2) running time. It doesn’t use any auxiliary temporary space though, so if you were in a situation where memory was extremely limited and you knew that you were only going to be dealing with small data sets then it might be your best option.

Second Solution

Let’s design a more efficient algorithm.

When we look at the first element in the array we see that it is a 5. We know that our target number is an 8. So with that information, what are we looking for? Well, we are searching the array for (8 – 5) which is 3. So for each element in our array, we want to quickly find out if there is an element equal to (target – current element).

What is the fastest way to find a value in our array? Using a Map of course. Maps rely on hash tables, and they are blazingly fast. The average lookup for a hash table is O(1) which means it happens in constant time no matter how much data you are working with. The worst case is O(n) but this will almost never be an issue if you have a partially decent hashing algorithm.

So the first thing we will do is populate a Map with the elements in our number array. The Map will consist of key/value pairs where the key is the element’s number and the value is a list of the locations in the array in which that element occurs.

Let’s look at our integer array and populate a Map to clarify.

For the array above, we would populate a Map that would look like this:

So for each number, we will keep track of the locations in the array where that number occurs.

Here is the pseudocode for our new algorithm:

This solution is much more efficient than our last solution. Populating the Map results in O(n) running time since we are looking at each element only one time. Iterating through the array again in order to find the locations of our number pairs also results in O(n), therefore our entire algorithm results in O(n) running time.

For this solution we are using O(n) auxiliary temporary storage since we are populating a Map. As long as the memory is available, this solution would be more favourable than the less efficient O(n2) solution.

Special Cases and Error Conditions

Our method will have the following definition:

We should check to make sure that our array is not null before we attempt to work with it.

Integer Overflow

If we are working with extremely large integers (either positive or negative) we might see false positives caused by integer overflow.

For example, let’s pretend that our array and target are defined as follows:

Our array holds a very large negative number as well as -1. Obviously in the real world, these two numbers cannot possibly add up to a large positive number. However, due to integer overflow, our algorithm will return a false positive in this case.

Let’s do an example with bytes in binary in order to better illustrate:

Solution in Java

GitHub – The source code for the final solution is available at GitHub.  Instructions for how to run the project locally are shown in the README.md document.

Here is the Main class that will implement the two solutions discussed.

Unit Testing

The following MainTest class will run unit tests to verify the functionality of the Main class.