DEV Community

loading...
Cover image for Two Sum Solution in JavaScript

Two Sum Solution in JavaScript

abmsourav profile image Keramot UL Islam Updated on ・2 min read

So what the hell is Two Sum? Well, it's a very popular Problem set in the world of Programming.

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

Basically what it saying is, you have an array and an integer. For example: [3, 2, 4] 6. Now add two items of the array and the result must be 6, 2 + 4 = 6. And don't forget that you can not add the same array item 3 + 3 = 6, you can't do this here :P.
When you get the result of the sum which is equal to the integer then return the index of those two array items as an array. So the index of 2 is 1, and the index of 4 is 2, and the result is [1, 2].

In JavaScript there are lot's of ways you can solve this, I will describe you two of them.

const twoSum = (nums, target) => {
    const 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);
                result.push(j);
                return result;
            }
        }
    }
}
console.log(twoSum([2, 4, 6, 5], 8)); // [0, 2]

Here we are finding which two array items create a sum that is equal to target integer, then store the index of those two items in an array and return that array.

Everything works fine here but what about Time Complexity. We are looping through the array twice, which means the Time Complexity is O(n^2). It's quite expensive, isn't it?

Okay, now let's see a better approach...

const twoSum = (nums, target) => {
    const result = [];

    for (let i = 0; i < nums.length; i++) {
        let diff = target - nums[i];
        let secondItemIndex = nums.indexOf(diff);

        // (secondItemIndex > -1) if array item is grater than target, then ignore that item
        // (secondItemIndex !== i) if same index, then ignore that item
        if ( secondItemIndex > -1 && secondItemIndex !== i ) {
            result.push(i);
            result.push(secondItemIndex);
            return result;
        }
    }
}
console.log(twoSum([2, 4, 6, 5], 8));

In this function mainly two thinks are happing, at first we are finding the difference between array item and target, 2 - 8 = 6. Then finding the index of that number in the array, nums.indexOf(diff).
The most important thing is in this scenario the Time Complexity is O(n), which is almost half of the previous one.

Discussion (3)

pic
Editor guide
Collapse
lukaszahradnik profile image
Lukáš Zahradník

The most important thing is in this scenario the Time Complexity is O(n), which is half of the previous one.

This is not true. The time complexity of the second approach is still O(n^2) as indexOf has to still go through whole array - separating inner loop into new function will not reduce the algorithm time complexity.
Also O(n) isn't "half of" the previous one (O(n^2)).

In the first example you should return the result when you find the indices, otherwise you can have array with length > 2.

Collapse
abmsourav profile image
Keramot UL Islam Author • Edited
  1. In the second function all happening in one loop, so time complexity is O(n). indexOf is an API method. It's way faster than a loop.
  2. Please run the first example and check the output.
Collapse
lukaszahradnik profile image
Lukáš Zahradník
  1. It's happening in two loops - one in your function and the second one in the indexOf. It is still O(n^2).
  2. Try out twoSum([2,4,6,5,6], 8) for both of your solution and you will see the inconsistency of outputs.