Two Sum Problem

You want to find 2 numbers that add up to the target and return their indices.

This is considered an easy interview problem, if you get it, god is watching over you.

Now, there are few ways to approach this: the brute force way (it'l work but it aint impressive), and then the optimal way. We will cover both.

The brute force way

Note: This will work, but make sure you can optimize it too.

The logic is as follows. We will use two for loops. The first will look through all the elements starting at the first element. Then next loop will go through all the elements starting at second element. If the two add up to the target, return the indicies of them. Relatively straightforward, but it takes up a lot of memory to run two for loops so it'l become more inefficient as the array grows. Nevertheless, here's the answer.

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

The efficient way

We don't want to use 2 for loops. Let's just use one.

What we'll do is create an empty object, and then we'll use forEach on the nums array. The forEach method can take in an element and its index, so we can set each set the element as the key and its index as its value.

`var twoSum = function(nums, target) {
 let obj = {}
 nums.forEach((num, index) => {
  obj[num] = index
 }


}`

Now we are going to loop through the nums array and use our one shot at a for loop.

var twoSum = function(nums, target) {
 let obj = {}
 nums.forEach((num, index) => {
  obj[num] = index
 }

 for (let i = 0; i < nums.length; i++) {
 let secondElement = target - element
 if (obj[secondElement] !== undefined && obj[secondElement] !== index) {
  return [index, secondElement]
  }
 }
}

Lets take a look at the example above.

We're looping through the numbers in the nums array and were saying, does the result of the target number minus the current element exist as a number here? That is, if the target is 9 and our nums array is [2, 7, 13, 15], does 9 - 2 exist? or does 9 - 7 exist? And is it not an existing element (we can use the same number twice)?

If so, return the element, and then the secondElement i.e the result of the target element minus the current element.

Comments

[Toby Parent]

Haven't benchmarked the difference, but I wonder about using a new Map() rather than an object, in terms of efficiency. From what I recall, for smaller arrays of numbers, the object literal is faster - but at a relatively small scaling, the Map() is faster access.

const twoSum = (numbers, target, map = new Map() ) =>
  numbers.some((number, index)=>{
    if(map.has(target-numbers[index]))
      return map.set('indices', [map.get(target-numbers[index]), index]);
    map.set(numbers[index], index) 
  }) && map.get('indices');

[Seth]

This solution would work too, I just prefer forEach, but thats the beauty of code - there are multiple right ways to solve a solution.