Two Sum Algorithm - JavaScript Tutorial/Solution

The Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Basic Solution

The brute force way of solving this would be looping through the array twice and adding up one number from each array to see if it equals the target. This is what it that looks like:

let twoSum = (nums, target) => {
    for(var i = 0; i < nums.length; i++) {
        for(var j = i + 1; j < nums.length; j++) {
            if(nums[i] + nums[j] == target) {
                return [i,j]
            }
        }
    }
}

This is inefficient simply because we have to do double the amount of work when looping through the same array twice. Although this will always work, as the array gets larger, the execution gets exponentially slower.

So let's take a look at how to go through this array only once.

Efficient Solution

First off, we need a way to keep track of all of the numbers we've already looked at as well as what numbers we need. We're going to do this by using a prevValues object to store our values which allows us to look at our numbers instantly without having to loop through the array again to see if the number exists. Take a look:

let twoSum = (nums, target) => {
// Create object to store values
  const previousValues = {}
  for (let i = 0; i < nums.length; i++) {
    const currentValue = nums[i]
    const neededValue = target - currentValue
// Store needed value as a key in the object
    const index2 = previousValues[neededValue]
// Check if we have an index that is equal to our needed value 
    if (index2 != null) {
      return [index2, i]
    } else {
// Store index for current value
      previousValues[currentValue] = i
    }
  }
}