Problem: Given an array of integers and a target sum, return every pair of integers that add up to the target sum.
The two-sum problem is a very common technical interview question. It is actually the very first problem on www.leetcode.com, which is a great resource to prepare for technical interviews. There are several ways to approach the problem so we will take a look at a few implementations.
Let’s examine the inputs first.
arr = [-4, 2, 1, 9, 7, 5]
target = 3
let twoSum = (array, target) => {
// code goes here
}
The first thing we should do is slow down and walk through the process in our heads. Here, you can see we have an array with 6 integers, and a target sum. What would you do first?
Here is my thought process upon first look…
Step 1 — Take first number in array, which in this case is -4
Step 2 — Look through the rest of the array for any number that, when added to -4, gives us the target, 3
Step 3 — If I find a number that satisfies the above condition, I will jot down the two numbers as a pair
Step 4 — Repeat steps 1 to 3 for the rest of the numbers in the array
So, how do we implement our thought process into code? Well what we are effectively doing is iterating through the array, and then for each element in the array, iterating through the array again to find any matches. Here is an implementation of what we call the naive solution or the brute-force solution.
let arr = [-4, 2, 1, 9, 7, 5],
target = 3
let bruteForceTwoSum = (array, sum) => {
let result = []
for (let i = 0; i < array.length; i++){
for (let j = i + 1; j < array.length; j++){
if (array[j] === sum - array[i]){
result.push([array[i], array[j]])
}
}
}
return result
}
bruteForceTwoSum(arr, target)
//[ [-4, 7], [2, 1] ]
The brute-force solution is not pretty. In fact, it has a time complexity of O(n²) because of our nested for loops. This is not optimal, but it works.
I personally find that it helps to get any kind of working solution first, then work on refactoring to hit better run-times.
So what we are doing here?
First we set up an empty array to the variable result. We begin our standard for loop and begin to iterate through our array.
Then, we initialize a second for loop and set the index variable j to to the index after i as you can see we set j = i + 1.
Next, we check to see if the element in the second loop is equal to the sum minus the element in the first loop.
If this is true, we will push the two numbers as a sub-array into the results array. Continue to do this and then return the array. As you can see indeed get the correct output, which means our implementation is correct.
Now that we have a working solution, let’s see another implementation. Perhaps, we can get achieve a better runtime.
Even though the following is technically not the solution an interviewer may be looking for, it is always fun to implement binary search in any algorithm. That’s how I feel, anyways. Assuming you already know how merge sort and binary search works…
Let’s write out the code for binary search, then we can we can discuss how we’ll use it for the two-sum problem.
let binarySearch = (sortedArray, num) => {
let start = 0,
end = sortedArray.length - 1,
mid
while (start <= end){
mid = Math.floor((start + end)/2)
if (num === sortedArray[mid]){
return mid
}else if (num < sortedArray[mid]){
end = mid - 1
}else if (num > sortedArray[mid]){
start = mid + 1
}
}
return false
}
Ok. So we got our binarySearch working in a way where it will return the index of the element we are looking for if it exists, otherwise it will return false. How does this help us?
Well, the idea is to iterate through the array once and for each element, find the difference between the element and the target/sum. Once we have that number we will run a binary search for it in the array. The cost of a binary search is O(log n). If our binary search function is able to find this number, it will return the index and then we can use that index to record it along with the current element. Continue iterating through the array(only once) and do that for each element. Bam! We now have our pairs. Here is the rest of the code.
let binarySearchTwoSum = (array, sum) => {
let sorted = mergeSort(array),
results = [],
indices = {}
for (let i = 0; i < sorted.length; i++){
let diff = sum - sorted[i],
binIndex = binarySearch(sorted, diff)
if (binIndex && !indices[i] && !indices[binIndex]){
results.push([sorted[i],sorted[binIndex]])
indices[i] = true
indices[binIndex] = true
}
}
return results
}
Note: in order to implement a binary search, our array must be sorted first. In this example we are using mergeSort to obtain our sorted array. You may have also noticed that we are mapping all pair indices separately. When checking to see if binIndex returns true, we are looking up the indices so as to avoid duplicate pairs. Since these lookups only cost us O(1), it is quite cost effective and is not affecting our performance. The average complexity here is O(n log n). Cool!
Last but certainly not least, we have the hash map solution. This is a pretty tricky way to do this but it does have an average complexity of O(n) which is awesome and way better than our original crummy solution.
let hashMapTwoSum = (array, sum) => {
let hashMap = {},
results = []
for (let i = 0; i < array.length; i++){
if (hashMap[array[i]]){
results.push([hashMap[array[i]], array[i]])
}else{
hashMap[sum - array[i]] = array[i]
}
}
return results
}
…and that’s it. What’s going on here anyway? So, we are iterating through the array only once and for each element we want to record the difference between the target/sum and element and set it as a key in the hash map. We set the value of that key to be the particular element. Once we continue iterating, we check to see if each element happens to be a key in our hash map. If that check passes, bingo! We have just run into an element that we require to create a pair. We then push the pair into our results array just like our other solutions. Deceptively simple yet beautiful, isn’t it?
Hopefully this gives a better, if not good, understanding of the two-sum problem and its implementation in JavaScript.