Explaining Leetcode’s Two Sum Problem (JavaScript)

This problem was particularly annoying, and insightful for me. The reason is that there are many ways to solve it. Finding a solution isn’t particularly difficult if you’ve been coding for a few months. Finding a reasonable solution that would be deemed acceptable in technical interview, was difficult for me. In this post, I’ll explain my approach to this relatively famous problem. We’ll explain the problem, come up with the most obvious implementation, and then find a more elegant solution.

The Two Sum problem states that given an array of integers, return indices of the two numbers such that they add up to a specific target. We can’t use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

We’ll start getting into solutions below.

The first, and most obvious solution is what’s called the iterative brute force solution, in which we iterate through every possible combination (in a worst-case scenario) until we find a solution.

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
}

In this case, we take the array (nums) and for each element of the array, we look at the next position of the same array (hence the nested loops). If the sum of these two numbers equals the target, great! We’re done, just return the positions of those two numbers in my respective loops. Simple enough.

Why is this not a good solution?

Typically, brute force solutions are easy to implement, and will always find a solution if one exist. But the tradeoff tends to be that they are computationally expensive, and may only even be implementable if we know that the size of the inputs are relatively small.

This algorithm can take a LONG time. In fact, in Big O notation, it’s quadratic, or O(n) squared time because, at worse case, we’d have to look at every single element of this array and do an operation of every other element of the array.

A nested loop tends to be a sign of optimization opportunities. So, how can we make it better?

Making it more efficient with extra caching and a little logic

As mentioned before, every algorithm has a trade off. A more efficient solution in terms of time, has the tradeoff that,

a) It requires more memory (i.e. space)

b) It’s a bit harder to conceptualize

Here’s an alternative approach that doesn’t have to iterate through the array more than once:

function twoSum(nums, target) {
let numObj = {};
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i];
    if (numObj[complement] !== undefined) {
      return [numObj[complement], i];
    }
    numObj[nums[i]] = i;
  }
}

Instead of looking for the sum of two numbers, which would be the obvious and intuitive approach, this approach takes each number, and looks for the number which when added to itself, would equalize the target (i.e the complement). For each number in the array, it creates this complement variable. If that complement number exists in the key:value object called numObj we created (i.e, it’s not undefined), then great! Return that number’s position in the object along with the position of number we’re looking at, and we’re done. If not, then add the number we’re looking at, and it’s position, in the numObj object.

It’s not as intuitive to come up with this solution, but you can quickly see, that at worse case, you’d only have to iterate through the entire array once. This makes the operation of finding the number we’re looking for much faster.

Thanks for reading!

And remember: grit > talent.