Two Sum Coding Interview Question

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.

Read More: Color Picker Question

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

First, we can use Brute force approach. We can loop through each element and add it to other element and check if sum is equal to target or not.

Here is the solution:

const twoSum = (arr, T) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i+1; j < arr.length; j++) {
      if (arr[i] + arr[j] = T) {
        return [i, j];
      }
    }
  }
}

In brute force we are using two for loops and thats why we are seeing O(n^2) Time Complexity. So instead of using two for loops, we can use only one for loop and store required value for each element store in has map to see if available in array or not.

Here is the solution with O(N) time complexity.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
  
    let output = [];
    let map = {};
    const len = nums.length;
    
    for (let i = 0; i < len; i++) {
      if (map[nums[i]]) {
        output.push(map[nums[i]] - 1, i);    
      } else {
          map[target - nums[i]] = i + 1;
      }
    }
    
    return output;
};

In this solution, While we iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table. If it exists, we have found a solution and return immediately.