Two Sum

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.

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

Let's start out with the skeleton problem.

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

We will start with a brute force method. In most cases if this were an interview it would probably be good enough to just talk through this example without actually implementing the code for it, but for the sake of completeness we will go ahead and implement it. We could solve this problem by nesting loops reading each number and then checking all of the remaining numbers to see if there is a match that would sum up to the target.

const twoSum = function(nums, target) {
  for (let i = 0; i < nums.length -1; i++) {
    const firstNum = nums[i];
    for (let j = i + 1; j < nums.length; j++) {
      const secondNum = nums[j];
	    if (firstNum + secondNum === target) {
	      return [i,j];
	    }
    }
  }
  return [];
};

Here we have a working first solution. It's a simple nested loop where we start the outer loop at the beginning of the array and keep track of the number we are on in a new variable. We then use the inner loop to run the remainder of the array checking if any item plus the item being tracked in the variable equals the target. If so we return the variable and the item. If no two numbers in the array equal the target we just return an empty array. Although this works, it has a runtime of O(n2). Let's see if we can do better if we use some form of hashmap. Let's create one.

var twoSum = function(nums, target) {
    let hash = {};
};

Next we will still need to iterate over the input array.

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

Inside the loop we need to check if there is a value that equals the target number minus the current number. If there is we can return the indices of the two numbers. If not we can then add the new number and it's index to the hash.

var twoSum = function(nums, target) {
    let hash = {};
    for (let i = 0; i < nums.length; i++) {
        const potentialMatch = taget - nums[i]
        // in js the number 0 is a falsey value
        // so if the index was 0 we need to account for that
        if (hash[potentialMatch] || hash[potentialMatch] == 0) {
            return [i, hash[potentialMatch]]
        } else {
          hash[nums[i]] =  i
        }
    }

};

Finally if we didn't find a matching pair we just need to return an empty array at the end.

var twoSum = function(nums, target) {
    let hash = {};
    for (let i = 0; i < nums.length; i++) {
        const potentialMatch = target - nums[i]
        // in js the number 0 is a falsey value so if the index was 0 we need to account for that
        if (hash[potentialMatch] || hash[potentialMatch] == 0) {
            return [i, hash[potentialMatch]]
        } else {
          hash[nums[i]] =  i
        }
    }
  return []
};

Using the hash we can do constant time lookups of the past numbers giving us a runtime of O(n). We have increased the space complexity here up to O(n) but we will see that sorting the array can help to minimize this issue when we get to Two Sum II.- Input array is sorted.