Two Sum Solution in JavaScript

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.

Comments

[Keramot UL Islam]

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.