DEV Community

Discussion on: The Two Sum Problem in JavaScript

Collapse
 
nathanbarrett profile image
Nathan Barrett • 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];

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...

Collapse
 
pappijx profile image
Ayush

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

Collapse
 
ndnam198 profile image
Nam Nguyen • Edited

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

Collapse
 
nathanbarrett profile image
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
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
shaileshcodes profile image
Shailesh Vasandani • 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 [];
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
Sloan, the sloth mascot
Comment deleted
 
shaileshcodes profile image
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.