# JavaScript Two Sum: Find All Pairs That Sum to a Target Value

**Question**: Given an array of integers and a target sum, find all pairs that add up to the target sum. Write a function `twoSum`

that solves this.

```
const arr = [7, 0, -4, 5, 2, 3];
twoSum(arr, 5); // [[0, 5], [2, 3]]
```

This question is an instance of the maximum subarray problem.

A related version of 2Sum is Highest Product of Two Numbers.

## Brute Force

A naive approach is to use two loops to iterate through `arr`

and check if each integer plus every *other* integer sums to the target value.

```
// O(n^2) time
const twoSum = (arr, target) => {
let results = [];
for (let i=0; i<arr.length; i++) {
for (let j=i+1; j<arr.length; j++) {
if (arr[j] === target - arr[i]) {
results.push([arr[i], arr[j]])
}
}
}
return results;
}
```

This solution works but at `O(n^2)`

time complexity we can do much better.

## Binary Search

A better approach is to **sort the array** and then use **binary search** to find our target sum. The built-in sort() array method has a time complexity of roughly `O(n log n)`

(the actual speed depends on the browser-specific implementation) and binary search is `O(log n)`

so our total time complexity is `O(n log n)`

.

Let’s start with our binary search function:

```
const binarySearch = (sortedArr, target) => {
let min = 0,
max = sortedArr.length - 1,
guess;
while (min <= max) {
guess = Math.floor((min + max) / 2);
if (sortedArr[guess] === target) {
return target;
} else {
if (sortedArr[guess] < target) {
min = guess + 1;
} else {
max = guess - 1;
}
}
}
return false;
}
```

Phew! It’s a bit of pain to type that all out and in a real-life interview I probably would just declare a helper function `binarySearch`

and move on.

Now we need to sort our array and use `binarySearch`

to find our target value.

```
// O(n log n) time
const twoSum = (arr, target) => {
let sortedArr = arr.sort(),
results = [];
for (let i=0; i<sortedArr.length; i++) {
let diff = target - sortedArr[i],
binaryIndex = binarySearch(sortedArr, diff);
if (binaryIndex) {
results.push([sortedArr[i], sortedArr[binaryIndex]]);
}
}
return results;
}
```

This solution works and at `O(n log n)`

is a big improvement over our brute force approach. It does display duplicates, which we could solve by adding a hash map. But we can do even better so let’s continue on.

## Greedy Approach

The best solution is to use a **greedy approach** which has a time complexity of `O(n)`

! We go through the array only once. For each element, we record the difference between our target and sum and set that as the *key* in an object. The value is the actual element at that point.

In other words we start with an empty object `{}`

, an empty array `[]`

for our solutions, and our sample `arr`

:

```
const arr = [7, 0, -4, 5, 2, 3];
let map = {};
let results = [];
```

Then we loop through the elements. For the first one `7`

we compute the difference between our target value `5`

and it; in other words `5 - 7`

which is `-2`

. So we create a key/value pair of `7: -2`

which tells us that if we see an element in the array that equals our value `-2`

then we have a match!

Now on to the second element `0`

, the difference is `5 - 0`

which is `5`

. Our new key/value pair is `5: 5`

. Our hash map now contains two entries: `{7: -2, 5: 5}`

. As we continue through the array, if we find an element that equals either `7`

or `5`

we have a result and push it into our `results`

array.

```
// O(n) time
const twoSum = (arr, target) => {
let map = {},
results = [];
for (let i=0; i<arr.length; i++) {
if (map[arr[i]] !== undefined) {
results.push([map[arr[i]], arr[i]])
} else {
map[target - arr[i]] = arr[i];
}
}
return results;
}
```

Note that given we have a `0`

in our input array, it will return falsy. Therefore we must check that `map[arr[i]]`

does not equal `undefined`

.

## Conclusion

It’s **very common** in questions of this type to work through the optimal solutions in this manner. First find a brute-force approach, then see if sorting would improve things, and finally **always consider a greedy approach** which uses either an array or a hash map to store values. Chances are the greedy approach is the best one.