Two Sum

Two Sum is one of the most frequently asked questions and quite a popular question in the community.

The task is to find a pair whose sum adds up to the target and you should return the indices of the numbers present in the pair

Prompt

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

//Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

//Example 2:
Input: nums = [3,3], target = 6
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 6, we return [0, 1].

Solutions

For this question, there can be multiple solutions but I am mainly focusing on 2 solutions i.e. a brute force and an optimized solution.

1) Brute Force Approach

const twoSum = (nums, target) => {

    /* brute force*/

    let output = []
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j <= nums.length - 1; j++) {
            let sum = nums[i] + nums[j]

            if (sum === target) {
                output.push(i)
                output.push(j)
                break
            }
        }
        if (output.length > 0) {
            break
        }
    }

    return output

};

const input= [2,7,11,15], target = 9
console.log(twoSum(input, target)) //[ 0, 1 ]

You will get the desired output using this approach but the time complexity will be O(n^2), where n is the length of the input array.

2) Using Objects / Map

const twoSum = (nums, target) => {

    /* using map*/

    const map = {}, output = []

    for (let i = 0; i < nums.length; i++) {

        let curr = nums[i]
        let diff = target - curr

        if (map[curr] !== undefined) {
            output.push(map[curr])
            output.push(i)
            break
        } else {
            map[diff] = i
        }

    }

    return output

};

const input= [2,7,11,15], target = 9
console.log(twoSum(input, target)) //[ 0, 1 ]

Ending Note

You can find the same problem on the LeetCode website.