This was an interesting problem I worked on, as it helped me get more familiar using a hash table to come up with a more efficient solution than if I had solved it using nested for loops. One of my close friends/mentor worked through it with me, and I owe him a great deal for being patient and providing great insight as I struggled through it initially. I found this problem on leetcode, a helpful site for practicing algorithms.
Problem
"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:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Input: nums = [3,2,4], target = 6
Output: [1,2]
Approach
We'll create an empty hash table where we'll pass in our key value pairs.
We'll be using a single for loop to iterate through our given array nums and passing in key value pairs into a hash table, which will be the elements (keys) and corresponding indices (values). The problem states that there is only one solution for a given array, so if our hash table contains the two indices corresponding to the elements that make up the target, we can stop there. However, in the worst case scenario, our hash table will contain every single element from the given array nums.
We figure out the difference by subtracting the current element we're looking at from the target and save that to a variable.
Next, we check if that key difference is in our hash table, and if it is, we will return the value of the key difference and the index of the current element we are looking at.
If the key difference is not in our hash table, then we assign the current element as a key in the hash table and its index as a corresponding value and continue looping.
Solution
First, declare an empty object, or hash table.
This is where we will pass in our elements and corresponding indices as key value pairs
var twoSum = function(nums, target) {
const mapper = {};
}
Next, we create a for loop to iterate through the array nums.
var twoSum = function(nums, target) {
const mapper = {};
//this is the hash table
for (let index = 0; index < nums.length; index++) {}
}
Inside the loop, we declare a variable difference, which we get by subtracting the element we're currently looking at in the array, nums[index] from the given target.
var twoSum = function(nums, target) {
const mapper = {};
//this is the hash table
for (let index = 0; index < nums.length; index++) {
let difference = target - nums[index];
}
}
Next, we check if difference is an existing key in our hash table mapper. If it is, we return mapper[difference] and the current index we are on.
var twoSum = function(nums, target) {
const mapper = {};
//this is the hash table
for (let index = 0; index < nums.length; index++) {
let difference = target - nums[index];
if (difference in mapper) {
return [mapper[difference], index]
}
}
}
Lastly, if our hash table mapper, does not contain the difference, then we assign a new key value pair in the hash table using the current element we're iterating through and its index.
var twoSum = function(nums, target) {
const mapper = {};
//this is the hash table
for (let index = 0; index < nums.length; index++) {
let difference = target - nums[index];
if (difference in mapper) {
return [mapper[difference], index]
} else {
mapper[nums[index]] = index;
}
}
}
This is a more efficient solution, giving us O(n) runtime than using a nested for loop which would have been a runtime of O(n^2). One last thing to remember is that the question is asking us to return the indices of the elements that sum up to target, not the elements themselves.
Top comments (0)