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.

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 guess;
    } 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.