DEV Community

EidorianAvi
EidorianAvi

Posted on

The Two Sum Problem in JavaScript

#javascript #beginners

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't optimize it to a requested time complexity. Turns out this is a super common problem and you will likely encounter it either in an interview or down the road practicing algorithms.

It's a pattern useful to recognize and it shows up in different types of problems so it's ideal to know how to tackle it if it ever rears its head.

The Problem

So the general gist of a two sum is that you have a list or an array of numbers and a target sum to hit. You're looking to return the indexes of the two numbers that when added together hit the target sum. There should only be one solution to the problem from the list of numbers and a number can not be used twice.

My first solution

Let's assume the input is:

  1. array = [1, 3, 10, 11, 14]
  2. goal = 13 

const twoSum = (array, goal) => {
    let indexes = [];

    for(let i = 0; i < array.length; i++){
       for(let j = i + 1; j < array.length; j++){
          if (array[i] + array[j] === goal) {
        indexes.push(i);
        indexes.push(j);
          }
       }
    }
    return indexes;
}
Enter fullscreen mode Exit fullscreen mode

This will return an array of [1, 2].

It works but if you check it out you'll notice it's running a loop inside of a loop to figure out which two numbers add up to the goal. That puts us at a time complexity of O(n^2). Pretty slow. Not a big deal for a small array like ours but it's far from optimized and I could say without a shadow of a doubt that if you're doing this type of problem they will be looking for you to improve the time complexity.

A more optimized solution

Lets assume the same input:

  1. array = [1, 3, 10, 11, 14]
  2. goal = 13 
const twoSum = (array, goal) => {
    let mapOfNumbers = {};
        let twoIndexes = [];

        for (let i = 0; i < array.length; i++) {
        mapOfNumbers[array[i]] = i;
    }

    for (let i = 0; i < array.length; i++) {
          let target = goal - arr[i];
      if(mapOfNumbers[target] !== null && mapOfNumbers[target] !== i) {
        twoIndexes.push(i);
            twoIndexes.push(mapOfNumbers[target]);
      }
        }

      return twoIndexes;
}
Enter fullscreen mode Exit fullscreen mode

Okay so let's talk about what's going on in this.

First thing is I mapped out the numbers and their indexes. I used the first for loop to accomplish this. Notice I assigned the number as the key and the index as its value.

Second thing is a ran a second for loop through the array and first determined what the value would have to be to equal to goal at that index.

Then inside that loop I do an if statement to check two things. One being if that target value exists in the map we created. The second making sure it's not at the same index as the one we are currently working with.

If they both pass then I push those two indexes into my output array and simply return it.

So while this one has two loops they're not nested so the time complexity lands at O(n) power. Much better.

Wrap Up

Okay so that's all I'm covering for today but if you have any questions at all feel free to reach out to me. I hope this is helpful to somebody in solving this problem you will no doubt encounter at some point. Happy Coding!

Top comments (19)

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

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 •

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) => {
  // ...
}
Enter fullscreen mode Exit fullscreen mode

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

Collapse
 
eidorianavi profile image
EidorianAvi •

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

Collapse
 
muhammedyousrii profile image
Muhammed Yousrii •

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

Collapse
 
eidorianavi profile image
EidorianAvi •

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

Collapse
 
chety profile image
Chety •

What about something like this?

function twoSum(arr,target) {
  const hash = {}
  for(let i = 0; i < arr.length; i++){
    const complement = target - arr[i]
    if(hash[complement] !== undefined && complement != arr[i]){
      return [hash[complement], i]
    }
    hash[arr[i]] = i
  }
  return undefined
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
adnenre profile image
Adnen rebai •

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 [];
  };
Enter fullscreen mode Exit fullscreen mode
Collapse
 
paul_levitt_2eb5cf3fbe227 profile image
Paul Levitt •

Not in the slightest;

1.

memo[array[i]] = complement;
Enter fullscreen mode Exit fullscreen mode

Here you’ve stored the compliment against the current value, ideally we’d want the index of the complement (ie memo[complement] = i)

2.

return [array.indexOf(complement),array.indexOf(array[i])];
Enter fullscreen mode Exit fullscreen mode

As already noted in above comments .indexOf will loop the array to find the matching value - so there are three loops here.

And actually, given the proposed update for #1, we already have both these indexes;

return [i, memo[complement]];
Enter fullscreen mode Exit fullscreen mode

Also;

if(memo[complement]){
Enter fullscreen mode Exit fullscreen mode

This only works when complement > 0

Collapse
 
timyip3 profile image
timyip3 •

thumb up for your readable code and explanation !

Collapse
 
eidorianavi profile image
EidorianAvi •

Thank you!

Collapse
 
debashishere profile image
DEBASHIS ROY •

test

Collapse
 
kiharasimon profile image
Simon Kihara • • Edited

I think you can add a break after executing the if condition to avoid duplication of indices

Collapse
 
ashm10 profile image
Asther Marie Moreno •

Love it, thank you!

View full discussion (19 comments)

Read next

tresorama profile image

Dynamic HTML Tag in React Components with the "as" prop

Jacopo Marrone @tresorama -

taiwo17 profile image

JavaScript's BEST KEPT SECRET is the Power of forEach Functions

Taiwo Shobo -

dumebii profile image

DevTools Startup Ideas: Build an AI-Powered Chatbot Using Claude And React

Dumebi Okolo -

mnboy profile image

Why Read/Write in Hash Maps Has O(1) Time Complexity⁉️🚀

Moein Salari -