Basic Algorithm Solving Strategies: Hash Maps
--
Today, I want to share one of my go-to algorithm solving techniques: hash maps.
Hash maps are a data structure that go by many names. In Python, we call them dictionaries. In Ruby, they are just called hashes. And, in JavaScript, we call them objects. Regardless of what you call them, however, they are a super common and super helpful data structure that will help us solve many different algorithms.
If you’d like to know more about what hash maps are please check out my previous blog as in this blog we are going to focus on seeing this data structure in action in a couple different algorithms!
Example One: Contains Duplicate
The first problem we are going to look over today is Contains Duplicate. The goal of this problem is, given an array of integers, determine if the array contains any duplicate numbers.
In order to solve this problem, we are going to take advantage of our hash map (aka object) data structure. We will use our object to keep track of the number of times an integer is repeated in our given array. Then, we can iterate through our hash map and if any number (aka our integer key) has a value greater than one, we know it has been repeated and we can return true. If no number is repeated, then our function can return false.
containsDuplicate = (arr) => {
if (arr.length === 0) {
return false
} let numHash = {}
for (let i = 0; i < arr.length; i++) {
if (numHash[arr[i]]) {
numHash[arr[i]] += 1
} else {
numHash[arr[i]] = 1
}
} for (let k in numHash) {
if (numHash[k]> 1) {
return true
}
}
return false
}
Example Two: First Unique Character in a String
The second problem we are going to take a look at today is LeetCode’s First Unique Character in a String.
The goal of this problem is, given a string, find the first non-repeating character and return its index. And, if no unique character exists, return -1.
Much like our above problem, to solve this problem we are going to again use our hash map/object data structure. Again like before, the first step to our solution will be constructing a hash map keeping track of how many times each character is repeated through in our string. Then, we can iterate through our hash map, see if any value has a value of 1 and, at the first instance, return the index of said value.
firstUniqueCharacter = (s) => {
let sMap = {}
//hash map
for (let char of s) {
if (sMap[char]) {
sMap[char] += 1
} else {
sMap[char] = 1
}
} for (let i = 0; i < s.length; i++) {
if (sMap[s[i]] === 1) {
return i
}
}
return -1
};
Conclusion
You’ve probably noticed how similar these two solutions are to one another and that was my point in writing this blog. By knowing how to construct and use a hash map in an algorithm, you will be able to quickly and easily solve a lot of problems!
As always, I’d recommend you finding some of your own practice problems as the best way to get better at anything is practice! Good luck and happy coding!
