This content originally appeared on DEV Community and was authored by Dhruvin
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 []
}
// Do not edit the line below.
exports.twoNumberSum = twoNumberSum;
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
This content originally appeared on DEV Community and was authored by Dhruvin
Dhruvin | Sciencx (2022-06-23T07:29:24+00:00) Crushing Job Interviews(DSA) – Two Number Sum. Retrieved from https://www.scien.cx/2022/06/23/crushing-job-interviewsdsa-two-number-sum/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.