a smarter twoSum solution
Published: 2019-02-19 04:18:47

---
title: a smarter twoSum solution
published: true
description: 
series: algorithms
tags: 
---

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:

```javascript
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!

```javascript
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:


```javascript
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!