Discussion on: The Two Sum Problem in JavaScript

[Nathan Barrett]

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];

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

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

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

[Shailesh Vasandani]

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 [];
}

[Shailesh Vasandani]

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]

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

[Nam Nguyen]

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

[Nathan Barrett]

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
}

[Mohamed Madbouly]

your solution is good but
Array.prototype.indexOf have time complexity o(n)
so your solution time complexity is o(n^2)