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

Problem

Write a function:

function solution(nums, target);

that, 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.

Examples

1. Given nums = [2,7,11,15], target = 9, the function should return [0,1].
2. Given nums = [3,2,4], target = 6, the function should return [1,2].
3. Given nums = [3,3], target = 6, the function should return [0,1].

Write an efficient algorithm for the following assumptions

• 2 <= nums.length <= 103
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

You can find the link of the question here.

Solutions

Brute force solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function solution(nums, target) {
  if (nums.length < 2) {
    return [];
  }
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
}

BigO Notation

Optimal Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
function solution(nums, target) {
  if (nums.length < 2) {
    return [];
  }
  const numsMap = {};
  for (let i = 0; i < nums.length; i++) {
    let curMapVal = numsMap[nums[i]];
    if (curMapVal >= 0) {
      return [i, curMapVal];
    } else {
      const numberToFind = target - nums[i];
      numsMap[numberToFind] = i;
    }
  }
  return [];
}

Explanation We have our numsMap which is a hashmap that contains key/value pairs. We create these key/value pairs based on figuring out what the numberToFind is when we look at each number in the array. The key is the numberToFind and the value is the index of the number we're currently looking at. This means that as we go through the array, we compare each number to see if it matches one of the numberToFind we've already created. If it already exists in our hashmap, then the value we get will be the index of element in the array that created the numberToFind which gives us our answer!

BigO Notation

Solution in Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        if len(nums) < 2:
            return []
        numsMap = {}
        for i, num in enumerate(nums):
            curMapVal = numsMap.get(num)
            if curMapVal is not None:
                return [curMapVal, i]
                break
            else:
                diff = target - nums[i]
                numsMap[diff] = i
        return []

The solutions above are pretty self-explanatory.

💌 If you’d like to receive more coding solutions in your inbox, you can sign up for the newsletter here.