Two Number Sum

Continuing on from my algorithm theme from last week, I thought id take a look at another very common algorithm that’s asked in interviews. This algorithm is a relatively easy one(as noted on hackerrank or LeetCode), and is a good place to start if your just getting into algorithms. Like any algo, there’s a few ways to solve this, so I thought we would go over a couple examples to find the best way to optimize our answer.

What is it?

So what exactly is the two number sum? Well the great thing is that this algo isn't to hard to get your head around, it typically requires you to return the indices or the numbers with-in an array to reach a targeted sum….

Problem Statement - Given an array of integers, return the indices of the two numbers whose sum is equal to a given target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

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

Brute Force — Hack it!

Easiest way to go about this is not the most elegant, nor the best as far as time complexity but non the less does provide a solution. You could use two four loops, in order to iterate over each number in the array twice to get the two indices that will return a solution. In the end this will give us a time complexity of O(n²)(where n² essentially represents the number of arrays being iterated), because we are having to iterate over this data twice, its not ideal or most optimized solution for this algorithm in terms of time complexity.

var twoSum = function (nums, target) {
  var indices = []; //empty array to created to store indices
for (var i = 0; i < nums.length; i++) { //first loop thru
   for (var j = i + 1; j < nums.length; j++) { //second loop thru
    if (nums[i] + nums[j] === target) {
      indices.push(i);  //adding indices too the new array
      indices.push(j);
    }
   }
  }
  return indices  //returning our new array with the correct indices
}
console.log(twoSum([2, 7, 11, 15], 9));

Map It!

If there’s is one good thing about computer science or programming is that there is always another way. In this next solution we will use a hash table(commonly referred to as a hash map), it will allow us to map over keys and values to find our solution. This will give us a time complexity of O(N) simply because worse case scenario we will only have to traverse our array of numbers once to get match them against the keys in our map.

var twoSum = function(nums, target) {
 var map = new Map();
for(var i = 0; i <nums.length; i++) {
    var num = nums[i];
    if(map.get(num) === undefined) map.set(target - num, i);
    else return [map.get(num), i];
 }
};
console.log(twoSum([2, 7, 11, 15], 9));

Alright lets break this down..

first we set up a way to check are values against the keys

var map = new Map();

second we create a for loop, this time we only loop thru the array once and set our nums to an index with-in the array

for(var i = 0; i<nums.length; i++) {
    var num = nums[i];

Finally we will check to see if those nums are in our Map, if they are not already inside we will add them, if they are already we will store that value against our key and then we continue on thru the loop.

if(map.get(num) === undefined) map.set(target - num, i);
    else return [map.get(num), i];

This will eventually run thru the entire array and return the result of the indices that make up the sum we are looking for…

console.log(twoSum([2, 7, 11, 15], 9));  
//[0,1] index

• Big O Notation
• ThnkFWD