Two Sum with an Optimized Solution

#coding #algorithms #devchallenge #interview

Coming back from my previous article: two sum problem

I mentioned that I would show another solution to reduce time complexity.

In the previous approach, I used two nested loops to check every possible pair of numbers in the array. This is essentially a brute-force method, where we try all combinations to find two numbers that add up to the target.

In this article, we will use a different approach. Instead of checking every pair, we use a hash map (object in JavaScript) to reduce the number of steps needed to find the solution.

Let’s take a look.

Question

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

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

You can return the answer in any order.

Example

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

Solution

function twoSum(nums, target) {
        const obj = {}

    for (let i = 0; i < nums.length ; i++) {
          const num = nums[i]
          const complement = target - num

          if (complement in obj) {
              return [obj[complement], i]
          }

          obj[num] = i
    }
};

const nums = [2, 11, 15, 7]
const target = 9

console.log(twoSum(nums, target)) // Answer: [0, 3]

Explain the solution

Create an object obj to store numbers we have already seen, along with their indices.
Loop through the array nums.
- For each element:
  - Store the current number in a variable num.
  - Calculate its complement using:complement = target - num
- Check if the complement already exists in obj:
  - If it exists, it means we have already seen the number that can pair with the current number to reach the target.
  - Return the indices:[obj[complement], i]
If the complement is not found:
- Store the current number and its index in the object:obj[num] = i
Continue the loop until the solution is found.