Solving Leetcode's #1 Problem

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.)

I was inspired by this Algorithm a Day series 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.

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].

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.

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!