Crushing Job Interviews(DSA) - Two Number Sum

The Question

Difficulty: Easy

Write a function that takes in a non-empty array of distinct integers and an integer representing a target sum. If any two numbers in the input array sum up to the target sum, the function should return them in an array, in any order. If no two numbers sum up to the target sum, the function should return an empty array.

Note that the target sum has to be obtained by summing two different integers in the array; you can't add a single integer to itself in order to obtain the target sum.

You can assume that there will be at most one pair of numbers summing up to the target sum.

Sample Input

array = [3, 5, -4, 8, 11, 1, -1, 6]
targetSum = 10

Sample Output

[-1, 11] // the numbers could be in reverse order

Optimal Space & Time Complexity:

O(n) time | O(n) space - where n is the length of the input array

The Thinking

If you paid attention to the boring maths professor's class, you might be able to come up with this solutions very easily.

So lets say

// 10 is the target sum
10 = x + y
// so
y = 10 - x

P.S: Hashmap is just a object in javascript or dictionary in python.

So now what we do is, we create a hashmap and iterate through the array that's given to us. Then we:

• check if the hash has y ie 10 - x
• if the value is there, then we return the array, since we have both x and y
• if not then we add that num to the hashmap

The Solution

function twoNumberSum(array, targetSum) {
    const nums = {} // this is the hashmap

  for (let num of array){
    if (nums[targetSum - num] ) return [targetSum-num, num]
    nums[num] = true
  }

  return []
}

Got any doubt's ? Got a better solutions ? Drop a comment below and let's start a discussion.

Follow me on instagram for more awesome content on coding: https://www.instagram.com/dhruvindev