Solving Leetcode's #1 Problem
Tags: algorithms, javascript
Published: 2020-08-01 00:09:51

The first problem on Leetcode's website is the "Two Sum Problem". It says that, if you're given an array of integers and a target, return the indices of the two integers in the array that add up to the target. Let's say that you were given the array `[2, 7, 11, 15]`, and the target `9`. The way to get to `9` is by summing the integers at index 0, `2`, and index 1, `7`, so the function should return `[0, 1]`. (You can find this problem [here](https://leetcode.com/problems/two-sum/).)

I was inspired by [this Algorithm a Day series](https://dev.to/alisabaj/series/7067) to go through solving this problem, step by step. Just as the author of the series does, I'll first talk about how I want to approach this problem. Then, I'll work through a solution to this problem, coding it in JavaScript.

## How to approach the Two Sum Problem
The brute force way to solve this problem is to have two nested loops. The first loop would go through each element of the array, and the inner loop would check every *other* element of the array, and see if their values sum to the target. This approach is considered "brute force" because it's not optimized, and therefore would be very slow.

Therefore, a better approach to the solution would be to only go through the array once, and to check what the "complement" of each element in the array is. By "complement", I mean what is the difference between that element and the target. For example, let's say we're given the array `[1, 2, 3]`, and the target `5`. The complement of the first element, at index 0, is `4`, because `5 - 1 = 4`. 

We can then build a hash. The keys of the hash will be the elements of the array, and their values will be the index in the array that that element is found. The reason we want to keep track of the index of each element is that the question asks for the **indices** of the two elements who sum to the target.

Rather than storing *every* element and its index in the hash, we can check if the "complement" for that element has already been found in the hash. If it has, then we know that those two elements sum to the target, and we can return those indices. 

This approach only requires us to go through the hash once, which would solve the problem in linear space (O(n)) and linear time (O(n)).

## How to solve the two-sum problem using JavaScript
The first thing I'll do is build an empty hash, which I'll just call `hash`. Then, I'll create a for loop, which will go through each element in the `nums` array.

```javascript
var twoSum = function(nums, target) {
    let hash = {};
    for (let i = 0; i < nums.length; i++) {
        //...
    }
};
```

Inside the for loop, I'll create a variable called `complement`. `complement` will be set equal to the difference between `target` and `nums[i]`.

```javascript
var twoSum = function(nums, target) {
    let hash = {};
    for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i]
        //...
    }
};
```

Now here is where the logic comes in. We want to see if the key `complement` is found in `hash`, which we can check with `if (hash[complement] !== undefined)`. If that's the case, then we can return an array of two elements: `i` and `hash[complement]`, which is equal to the index of the element `complement` in `hash`.

Otherwise, if `complement` is not a key in `hash`, then we can simply initialize a key in `hash` whose key is the element we're currently on, and value is the index, `i`.

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

Feel free to let me know if you have questions about how I solved this!