Solving the two sum algorithm

Perhaps one of the most common algorithms is the “two sum” algorithm from leet code. It is said to be a commonly asked entrance level technical interview question. It reads

“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.”

and their example of the stated problem:

I find this algorithm to be a great foundation of learning how to use a hash table to assess an array of data with a decent time complexity.

On a first attempt the brute force method might be to iterate over the nums array and select an integer and add it to every remaining integer, looping through the whole array until our target is achieved if ever. However, that would require nesting two for loops which is quite inefficient.

After literally searching “how to solve algorithms” I found an awesome guide video by Kyle Cook at web dev simplified where he steps through solving this problem with a hash table.

To begin, it’s best practice to pseudo code. What do we know? We do know that we need to at least loop through the array once, and we know that we want to create a hash table to store our data as to not iterate through the array again. We can start about here

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

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

We also know that we can find out what integer we need to reach the target in addition to the index we’re currently on, by subtracting our current index value from the target. Or more simply “Target — index= needed value”

i.e if we’re on index 0 (2) we know that 9–2 =7. Therefore the index of 7 (which is 1) is the next index we must find and return. So in code form we have a current index selected with a variable (currentNum) and a variable to do the math of what number we need.

nums = [2,7,11,15] target = 9
var twoSum = function(nums, target) {
let output = {}
 for(let i = 0; i < nums.length; i++){
   const currentNum = nums[i]  
   const neededNum = target - currentNum
}

This is where the has table (and quite honestly the most confusing part) comes in. What we need to do is store our current index as a key, with a value of a needed number. So if target is = 9 and we’re currently at index 0, which has a value of 2, so we need the index that has a value of 7 (in this case that index is 1).

What really helped me grasp this concept was visualizing what the completed output hash would look like even if the condition for a solution was met.

nums = [2,7,11,15] target = 9
var twoSum = function(nums, target) {
let output = {}
 for(let i = 0; i < nums.length; i++){
   const currentNum = nums[i]  
   const neededNum = target - currentNum
//output = { 7:0, 7:2, -2:2, -6:3 }

Now all we need to do is find a second value to go with the current index we’re on to add up to the target. Since we have an index variable, we can assume that at some point through iteration our currentNum will be at least one half of the solution. Therefore, we can say “The second value is equal to the value in our output hash that is stored at a key of the number we need.” But since we want to build this hash as we iterate, we set up a condition that says if this second value does not exist within our hash make a new key value pair equal to that.

Or in code form:

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

So that’s it. Thanks for reading and happy hacking!