2sum LeetCode Solution: JavaScript

I haven’t done any blog posts on data structures or algorithms so I thought I would cover a solution to one of the more popular questions people may see on a technical interview: 2sum. This solution was 60.1% faster than all other submissions, and 29% less memory storage used. So in an interview, it may be wise to ask some probing questions determining which is more important to them, speed or memory?

Here is the question prompt:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Let’s start working through our solution. In this case I am going to use a hash map to store the numbers we come across. We are checking through our nums array where the keys are the numbers in the array and the value is their corresponding index.

var twoSum = function(nums, target) {
    const previousNumbers = {};
    }

We know we want to loop through our nums so let’s define some key variables.

var twoSum = function(nums, target) {
    const previousNumbers = {};
    for(let i = 0; i < nums.length; i++) {
        const currentNumber = nums[i];
        const numberNeeded = target - currentNumber
        const index2 = previousNumbers[numberNeeded]
  }
}

So we are iterating through our array, and we are keeping track of some values along the way.

currentNumber = the current number we are on during our loop.

numberNeeded = this is the our target subtracted by our currentNumber. This gives us the second number we need in our 2sum. In other words, the current number plus this number will reach our target.

index2 = as I mentioned before, we are going to be storing each number within our hash map ‘previousNumbers’, the second value for our final solution is ‘index2’ which is equal to previousNumbers[numberNeeded]. This will return the index we need for the solution.

Last step…

nums = [2,7,11,15] target = 9
var twoSum = function(nums, target) {
    const previousNumbers = {};
    for(let i = 0; i < nums.length; i++) {
        const currentNumber = nums[i];
        const numberNeeded = target - currentNumber
        const index2 = previousNumbers[numberNeeded]
     if (index2 != null) {
        return [index2, i]
    } else {
            previousNumbers[currentNumber] = i
        }
    }
}

Let’s break this down.

In this example let’s walk through what happens in each iteration.

First Iteration:

currentNumber = 2;
numberNeeded = 7; (9 - 2 = 7)
index2 = previousNumbers[7] === null(does not exist yet)
*we will hit our else statement first iteration*
previousNumbers[2] = 0
previousNumbers = {
2:0
}

2nd Iteration:

currentNumber = 7;
numberNeeded = 2; (9 - 7 = 2)
index2 = previousNumbers[2] = 0
*since index2 has a value this iteration our first condition is satisfied and we return a solution!*
return [index2, i]     --  index2 = 0 and i = 1

previousNumbers = {
2:0
}

Hopefully that gave a more clear look at what is happening through each iteration. While I am sacrificing some storage as I am creating an object, I am only iterating through our nums array one time. More speed, but also larger memory, there are always trade offs! Hope you enjoyed and thought this solution was a cool approach!