👋
Welcome to my blog!

Two Number Sum

Discover the optimal solutions to the classic problem of finding two numbers that add up to a specific target sum.

Two Number Sum
array
easy

Published At

6/3/2021

Reading Time

~ 4 min read

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

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

Sample Output

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

Hints

Hint 1

Try using two for loops to sum all possible pairs of numbers in the input array. What are the time and space implications of this approach?

Hint 2

Realize that for every number X in the input array, you are essentially trying to find a corresponding number Y such that X + Y = targetSum. With two variables in this equation known to you, it shouldn't be hard to solve for Y.

Hint 3

Try storing every number in a hash table, solving the equation mentioned in Hint #2 for every number, and checking if the Y that you find is stored in the hash table. What are the time and space implications of this approach?

Optimal Space & Time Complexity

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

Solution-1
javascript
function twoNumberSum(array, targetSum) {
  // array of length n
  if (array.length === 0) return
 
  for (let i of array) {
    // first n iteration
    for (let j of array) {
      // secind n iteration
      if (i === j) continue
      if (i + j === targetSum) return [i, j]
    }
  }
  return []
}
 
// O(n ^ 2) time, since there are two iterations of array in this solution.
// O(1) space, since all is just temporary space.
 
//  O(n ^ 2) | O(1)
Solution-1
javascript
function twoNumberSum(array, targetSum) {
  // array of length n
  if (array.length === 0) return
 
  for (let i of array) {
    // first n iteration
    for (let j of array) {
      // secind n iteration
      if (i === j) continue
      if (i + j === targetSum) return [i, j]
    }
  }
  return []
}
 
// O(n ^ 2) time, since there are two iterations of array in this solution.
// O(1) space, since all is just temporary space.
 
//  O(n ^ 2) | O(1)
Solution-2
javascript
function twoNumberSum(array, targetSum) {
  // array of length n
  const nums = {}
  for (let num of array) {
    // first iteration of n
    let potentialMatch = targetSum - num
    if (potentialMatch in nums) {
      return [potentialMatch, num]
    } else {
      nums[num] = true
    }
  }
  return []
}
 
// O(n) time, wow this solution is just awesome.
// O(n) space, since we are creating a dict of nums
Solution-2
javascript
function twoNumberSum(array, targetSum) {
  // array of length n
  const nums = {}
  for (let num of array) {
    // first iteration of n
    let potentialMatch = targetSum - num
    if (potentialMatch in nums) {
      return [potentialMatch, num]
    } else {
      nums[num] = true
    }
  }
  return []
}
 
// O(n) time, wow this solution is just awesome.
// O(n) space, since we are creating a dict of nums
Solution-3
javascript
function twoNumberSum(array, targetSum) {
  array.sort((a, b) => a - b)
  let left = 0
  let right = array.length - 1
 
  while (left < right) {
    // sum of left index and right index
    let currentSum = array[left] + array[right]
    if (currentSum === targetSum) {
      return [array[left], array[right]]
    } else if (currentSum < targetSum) {
      left++
    } else if (currentSum > targetSum) {
      right--
    }
  }
  return []
}
Solution-3
javascript
function twoNumberSum(array, targetSum) {
  array.sort((a, b) => a - b)
  let left = 0
  let right = array.length - 1
 
  while (left < right) {
    // sum of left index and right index
    let currentSum = array[left] + array[right]
    if (currentSum === targetSum) {
      return [array[left], array[right]]
    } else if (currentSum < targetSum) {
      left++
    } else if (currentSum > targetSum) {
      right--
    }
  }
  return []
}

🍉

Do you have any questions, or simply wish to contact me privately? Don't hesitate to shoot me a DM on Twitter.

Have a wonderful day.
Abhishek 🙏

Join My Exclusive Newsletter Community

Step into a world where creativity intersects with technology. By subscribing, you'll get a front-row seat to my latest musings, full-stack development resources, and exclusive previews of future posts. Each email is a crafted experience that includes:

  • In-depth looks at my covert projects and musings to ignite your imagination.
  • Handpicked frontend development resources and current explorations, aimed at expanding your developer toolkit.
  • A monthly infusion of inspiration with my personal selection of quotes, books, and music.

Embrace the confluence of words and wonder, curated thoughtfully and sent straight to your inbox.

No fluff. Just the highest caliber of ideas.