a smarter twoSum solution

Y'all are familiar with the twoSum problem, right? The gist of it is this: You get an array of numbers, and a target sum (a number), and you want to see if any pair of numbers in your array will add up to the given target sum.

One obvious solution is that you can simply iterate over the array and add all possible combinations of the numbers, check if they're equal to the target, return true if they are, and return false if you get through the array without finding a match. It looks something like this:

function twoSum(arr, target){
    for (let i = 0; i < arr.length; i++){
        for(let j=0; j < arr.length; j++){
            if (i !== j){
                if(arr[i] + arr[j] === target){
                    return true;
                }
            }
        }
    }
    return false
}

Obviously that's a mess. it's got about 5 levels of nesting. it's unreadable, and it's also inefficient. We can do better than that.

Right now, we're adding arr[i] with every element that is not itself. This is a problem, because it means we're actually duplicating our work. Let's say we have a set that consists of [1, 2, 3, 4, 5]. If we've already checked 1+2, 1+3, 1+4, and 1+5, we don't need to check 2+1, 3+1, 4+1, or 5+1!

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

you'll notice that setting j to i+1 allows me to avoid having a second conditional. Now we're only doing the combinations of numbers that we actually need to do, which is definitely a big improvement! However, we're still looking at nested 'for' loops, which really mess up the speed of our algorithm as the size of our data grows. In terms of time complexity, this particular solution resolves in O(n^2) time.

Let's go ahead and introduce a new idea.

We're checking if arr[i] + arr[j] = target, right? Well, we can also frame that as checking if arr[j] = target - arr[i]. While it may not be completely obvious how this might help us, we can at least take a look at this next solution:

function twoSum(arr, target) {
  const numbers = {};
  for (let i = 0; i < arr.length; i += 1) {
    if (numbers[arr[i]] === true) return true;
    const complement = target - arr[i];
    numbers[complement] = true;
  }
  return false;
}

Big change, huh?

The coolest thing is that we can do the whole thing in one run, meaning it's O(n) time. Let's look at how that's possible. First, we create an object that we're calling "numbers". This object is used to store our complements as we go. These are represented in our keys.

Back to our previous point, item A = target - itemB. so, if we use a key of target - itemB, we can simply access our object to see if it has that particular key.

Let's take the example of an array, [3, 7, 12, 1, 2, 5] with a target of 5. Our first step is to look at the 3. It's the first number we hit. 5 (our target) - 3 (our number) = 2 (our complement), so that means that if we ever see a 2 in our array, we know that we have a sum that adds up to the target.

Our object looks like this: {'2': true}.

Let's look at the next number, 7. First, we check its value on our numbers object. numbers[7] resolves to undefined, so we know that it's not the sum we're looking for. So, we find the complement, 5-7 and store it on our object.

Now, the numbers object looks like this: {'2': true, '-2': true}.

And we continue, checking if the item in our array is a key on our object and storing its complement on our object if it isn't. Eventually we'll hit the 2. When we do, our object will look like this: {'2': true, '-2': true, '-7': true, '4': true}. So we check numbers[2], and get true, breaking us out of the loop and telling us that our array does, indeed, include two numbers that add to 5.

If we never hit a sum, we get to the end of the array, the loop ends, and we simply return 'false'.

easy!

Addendum: If the numbers object looks a little weird to you, that's because it is. ES6 introduces the Set, which has an add and a has method that run in O(1) time. It can be a great alternative to the syntax that I'm using here!