Using Hash Maps in Algorithmic Problems
Last week, I touched up on a few essential hash map methods. This week, I’ll be going through a LeetCode algorithm problem that I worked on in which I implemented a hash map.
Two Sum is an easy-level algorithm problem with the following prompt:
“Given an array of integers
nums
and an integertarget
, return indices of the two numbers such that they add up totarget
.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.”
They provided a number of examples, but here is the first example:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
var twoSum = function(nums, target) {
// creating a new Map
let map = new Map;// creating variable 'i' for the for loop
var i;// for loop; setting i to 0 (1st index in the hash map), // conditional, increment i value to continue the for loop
for (i=0; i < nums.length; i++) {// setting variable 'complement' to look for numbers in nums that // are equal to the complementary value to reach target
let complement = target - nums[i];
// if statement to find if the map contains the complement number
if (map.has(complement)) {// if it does, then get the index of the complement in the map
// return that as an array with the current index we're on
return [map.get(complement), i]
}// if it doesn't meet if statement, set the new num into the map
map.set(nums[i], i)
}
};
As shown here, I utilized a hash map and a for loop. I started off by initializing a map. Then, I use a for loop to go through each number in the given nums
array. In the loop, I either look for the complement number or add a new value into the map. As it goes through each value of the array, it searches for the complementing number that will add up to the given target
value.
As this is just an easy-level problem, the use of a hash map was simple and easy to follow. However, as I approach more higher-difficulty problems that utilizes a hash map, I’ll update and add on to this post!