DEV Community

The Two Sum Problem in JavaScript

EidorianAvi on January 25, 2021

The very first technical question I got asked was the classic two sum algorithm problem. I was fresh to algorithms and could solve it but I couldn'...

Read full post

Nathan Barrett • Jan 25 '21 • Edited

Great explanation. Under a time constraint pressure I would have undoubtedly gone with the nested arrays solution. The optimized solution you have there is better (considering the problems rules we must abide by). But after thinking about it, the first loop you have there is unnecessary because you are just remapping it to quickly find the index of the difference between the array number and the goal. Array.prototype.indexOf will do that for you. Here is an even more optimized solution coupled with an early return.

const input = [1, 3, 10, 11, 13];

console.log(twoSum(input, 13)); // outputs [1,2]

codesandbox.io/s/keen-browser-hmsp...

Shailesh Vasandani • Jan 25 '21 • Edited

Nice solution! I like the early return, that way the solution doesn't double up on the numbers.

However, I think that indexOf actually runs in O(n) time, because it has to search through the array for the specified number. That means your solution is still O(n^2), because it has two nested loops.

I think the most optimized would be a mix of both, so:

const twoSum = (array, goal) => {
  let numberMap = new Map();

  for (let index = 0; index < array.length; index++) {
    el = array[index];

    if (numberMap.has(goal - el)) 
      return [index, numberMap.get(goal - el)];
    else numberMap.set(el, index);
  }

  return [];
}

Comment deleted

Shailesh Vasandani • May 3 '21

Thanks for your reply! Since it was more of a conceptual answer, I didn't run it before commenting. I have now; I figured out the error and fixed it.

For those interested, the issue was that a return statement in a forEach loop actually just returns inside the loop, and doesn't return in the function. To fix it, I converted it to a plain for loop.

As for the 5 people who liked it, I'm sure they appreciated the concept behind the comment and could see past any logic errors. I don't think that quite makes them fools.

Ayush • Feb 24 '22

indexOf uses forloop internally so the time complexity of your code becomes O(n^2).
Instead use map for this solution.

Nam Nguyen • Dec 6 '22 • Edited

Your solution will fail with test input
[1, 5, 5, 4, 9]
10
since method indexOf stops immediately at the first match

Nathan Barrett • Dec 6 '22

No it does not. It correctly outputs [0, 4]. But I see where you are going with it, change that last value from 9 to 10 so that only the two 5 values will work. It still outputs [2, 1] which are the indices of both 5 values. Why? Because even though it won't catch it on the first five it comes across it will catch it on the second. But you bring up a good point. Can we optimize this so that you don't have to keep going through the array if the solution is a duplicate value that is AFTER the index you are currently on? Yes. And here is my solution for that.

function twoSum(array, target) {
  for (let i = 0; i < array.length; i++) {
    const searchArray = [...array];
    searchArray.splice(i, 1);
    let diffIndex = searchArray.indexOf(target - array[i]);
    if (diffIndex >= 0) {
      return [i, diffIndex >= i ? diffIndex + 1 : diffIndex - 1];
    }
  }
  return []; // no solution found
}

Shailesh Vasandani • Jan 25 '21

Awesome post! Using an Object is a great way to ensure it runs in O(n) time.

Also, a tip I learned for making code blocks a lot easier to read is to take advantage of syntax highlighting; i.e. instead of using just the three backticks, put the language after it. It's hard to show in markdown, but something like this: ` ` `javascript.

That should give something like this:

const twoSum = (array, goal) => {
  // ...
}

Thanks so much for sharing! Your code is super readable and your explanations are very understandable.

EidorianAvi • Jan 25 '21

Oh that's amazing I will definitely be using that thank you!

Muhammed Yousrii • Jan 25 '21

Bravo, so simple and powerful,

The result of the previous example will be [1, 2, 2, 1]
So we need an solution for it,

We can break the array once the goal is achieved, Or to union the returned array using following expression

return [... new Set(...twoIndexes)]

another thing along side the above improvment which can improve performance of your solution is like you know JS return false for falsy values and 0 considered falsy value even it's a real value like 0

So we need to replace the first part of the IF condition to be
mapOfNumbers[target] != null Instead of mapOfNumbers[target]

Because what if index of the target is 0 ? it will return false
so we continue looping through the array for no reason

EidorianAvi • Jan 25 '21

Great catch and a super good point! I'm going to edit that into the post much appreciation.

Adnen rebai • Dec 1 '22

best solution with just one for loop

/**
 * GET INDEXS OF NUMBER WHERE TWO NUMBER FOR ARRAY EQUAL GOAL
 * @param array - array of number
 * @param goal  - number
 * @returns 
 */
 const twoSum2 = (array, goal) => {
    let memo = {};
    let complement;
    for (let i = 0; i < array.length; i++) {
      complement = goal - array[i];
      memo[array[i]] = complement;

      if(memo[complement]){
          return [array.indexOf(complement),array.indexOf(array[i])];
      }
    }
   return [];
  };