Introduction

The two-sum interview question is interesting to explore because it has both a brute force, logical solution, as well as a more time-efficient solution that can demonstrate strong computer science fundamentals. Let’s explore both potential solutions and hopefully learn along the way!

The Two-Sum Question

First, let’s understand the two-sum question. It’s usually posed as some form of the following:

You are asked to create a function that takes two parameters. The first parameter, nums, is an array of numbers. The second parameter, total is a single number. The output of the function should be a two-element array that represents a pair of numbers in nums that add up to total.

/**
 * @param {number[]} nums
 * @param {number} total
 * @return {number[]}
 */
const twoSum = (arr, total) => {
  // Solution here
};

Typically, we’re given a couple examples of valid input/output combinations:

input: nums = [1, 2, 3], total = 4
output: [1, 3]

input: nums = [3, 9, 12, 20], total = 21
output: [9, 12]

A Quick Note on Solving Coding Challenges During an Interview

If you’re solving any coding challenge during an interview, it would be prudent to ask some clarifying questions before you start solving the problem. In the two-sum case, you might want to ask the following questions (and probably some others I can’t think of):

• Can nums ever be anything other than an array of numbers?
• Can total ever be anything other than a number?
• Will there always be two numbers in nums that add up to total? If not, what should the output be when there is no solution?

For the purpose of this blog post, we will assume nums will always be an array of numbers, total will always be a number, and there will always be a solution to the problem (i.e., two numbers in nums will always add up to total).

Brute Force the Solution

Our first instinct will likely be to brute force the solution. To do this, we can use the following procedure:

• start with the first element of nums and iterate through each of the remaining elements of the array, checking if they add up to total
• move on to the second element of nums and iterate through each of the remaining elements, checking if they add up to total
• repeat until the matching sum is found!

In code, we’ll implement this as a nested loop:

/**
 * @param {number[]} nums
 * @param {number} total
 * @return {number[]}
 */
const twoSum = (nums, total) => {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === total) {
        return [nums[i], nums[j]];
      }
    }
  }
};

console.log(twoSum([1, 2, 3], 4)); // [1, 3]
console.log(twoSum([3, 9, 12, 20], 21)); // [9, 12]

Awesome! There are a couple potentially tricky aspects of this solution; let’s quickly explore them.

Why does the outer loop stop at i < nums.length - 1?

The outer loop doesn’t have to account for the last element of the nums array, just the second-to-last element of the array. The nested loop will account for the final element.

Why does the nested loop start at j = i + 1?

As we described above, the outer loop starts at one position in the array and the inner loop only needs to start with numbers occurring later in the array. Any combinations including earlier numbers in the array have previously been attempted.

The Problem with the Brute Force Approach

Solving two-sum the brute force way is great. It demonstrates solid reasoning and coding skills. That being said, it’s helpful to be able to articulate what’s wrong with any solution: awareness of your software’s limitations and the associated computer science fundamentals is both impressive to prospective employers and important as you grow as a developer.

So what’s the problem? Nested loops open us up to O(n²), or quadratic, time complexity.

Understanding O(n²) time complexity

Essentially, O(n²) time complexity means the time to execute the algorithm is proportional to the square of the number of inputs. This becomes obvious when we look at our brute force approach: if we add an element to nums, our solution has to go through an additional element in each of the nested loops and then has to do an additional time through the entire double loop.

Let’s do an experiment to see this add up. We will create an array with 100,000 elements with the solution nums being the final two elements.

const len = 100000;
const bigArr = new Array(len).fill(1);
bigArr[len - 2] = 9;
bigArr[len - 1] = 10;
const total = 19;

Now lets implement our brute force two-sum solution, but this time we’ll keep track of how many iterations it takes as well as roughly how long it takes.

const twoSum = (nums, total) => {
  let iterations = 0;
  const startTime = new Date();
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      iterations++;
      if (nums[i] + nums[j] === total) {
        console.log(
          `Iterations: ${iterations}`,
          `Time: ${new Date() - startTime}ms`
        );
        return [nums[i], nums[j]];
      }
    }
  }
};

twoSum(bigArr, total);
// Iterations: 4999950000 Time: 20032ms

The brute force solution went through almost 5 billion iterations and, on my computer, took 20 seconds. Yikes! Let’s see if we can do better.

The Power of Objects (and, More Importantly, Hash Tables)

We can, in fact, do better. Rather than creating a nested loop, let’s just go through the nums array once. To keep track of the array elements we’ve already seen, we’re going to add them as keys to an object. For each element of the array, we check if the complementary key exists in our object.

That may have been confusing in paragraph form, so here’s the code!

const twoSum = (nums, total) => {
  // Keep track of previous array values
  const previousValues = {};

  for (let i = 0; i < nums.length; i++) {
    // What previous value needs to exist for
    // us to have found our solution?
    const complement = total - nums[i];

    if (previousValues[complement]) {
      return [complement, nums[i]];
    }

    // This current array item now becomes
    // a previous value
    previousValues[nums[i]] = true;
  }
};

console.log(twoSum([1, 2, 3], 4)); // [1, 3]
console.log(twoSum([3, 9, 12, 20], 21)); // [9, 12]

You may be thinking: we only have one loop, sure, but our second loop is replaced by this previousValues[complement] lookup. Is that really so much more efficient than a second loop?

The answer is yes because object lookup is O(1) time complexity. This is due to JavaScript’s use of hash tables in objects! For a great primer on hash tables, see this excellent post.

Since the object lookup is O(1) and the loop is O(n), our functions time complexity is now O(n). Let’s try our new algorithm out on the same big array we used before.

const len = 100000;
const bigArr = new Array(len).fill(1);
bigArr[len - 2] = 9;
bigArr[len - 1] = 10;
const total = 19;

const twoSum = (nums, total) => {
  let iterations = 0;
  const startTime = new Date();

  const previousValues = {};
  for (let i = 0; i < nums.length; i++) {
    iterations++;
    const complement = total - nums[i];
    if (previousValues[complement]) {
      console.log(
        `Iterations: ${iterations}`,
        `Time: ${new Date() - startTime}ms`
      );
      return [complement, nums[i]];
    }
    previousValues[nums[i]] = true;
  }
};

twoSum(bigArr, total);
// Iterations: 100000 Time: 4ms

Much, much faster.

Nothing’s Free

While we decreased our time complexity, we increased our space complexity since we need to create a new object, previousValues, in memory. For very large objects (e.g., on the order of a million elements), we’re talking about 10MB of memory. Not trivial, but likely worth it to save on time complexity!