Just Throw a Hashmap at it!
Can’t find an optimal algorithm for a problem? Just throw a HashMap at it!
Let me start by saying that obviously, a HashMap isn't the solution to all your data structure and algorithm challenges; I am only referencing a popular joke within the coding community. This is not to say that HashMaps are not helpful. In fact, HashMaps are quite convenient for solving many of the problems you may encounter on Leetcode, on your own projects, at work, and even in interviews. I would also like to preface this by mentioning that I know HashMaps can seem intimidating at first (as they did for me) but can be quite user-friendly and understandable.
What is a HashMap?
You may be wondering to yourself: “What is a HashMap”? A HashMap is a data structure found in almost every programming language that holds a set of key-value pairs. An easy way to visualize this is to think of a menu where the keys are Menu items and the values are the Prices. It can be visualized like this:
| Menu Item | Price|
|-----------|------|
| Burger | 6.99 |
| Fries | 2.99 |
| Shake | 4.99 |
| Soft Drink| 1.99 |If I wanted to get the price of burger, I could provide the key of “burger”, and the associated value of 6.99 would be returned as the output. In context, say for example you created a small program to give you menu items less than 5 dollars. We can use the HashMap we created to quickly look up the items in the map which are less than $5 resulting in Shake, Softdrink, and Fries being returned, assuming all goes well. It is also worth mentioning that HashMaps have a constant look-up time at O(1). This means that regardless of the size of the data set, the amount of time it takes to find any element is still a fixed amount, so if you are looking to speed up your algorithm, this could be a solid approach if the data structure is applicable to the problem you are solving.
Key Takeaways:
- HashMaps are a data structure containing sets of key-value pairs
- Have a constant lookup time of O(1)
- Can create associations of random objects with other objects
- Useful in a variety of ways to create efficient algorithms
Now let's dive into a classic Leetcode problem and see this in action
The challenge we are facing today is Most Frequent Even Element:
Given an integer array nums, return the most frequent even element. If there is a tie, return the smallest one. If there is no such element, return -1.
Example 1:
Input: nums = [0,1,2,2,4,4,1]
Output: 2
Explanation:
The even elements are 0, 2, and 4. Of these, 2 and 4 appear the most.
We return the smallest one, which is 2.Example 2:
Input: nums = [4,4,4,9,2,4]
Output: 4
Explanation: 4 is the even element that appears the most.Solution:
The first thing we need to consider when approaching this problem is that in the case there is a tie, we need to return the smallest element. If we want to avoid looping twice (to save time) we need to create two variables to hold the most amount of times a number that fits the criteria is repeated and another variable to hold the number itself (we can also break a tie using this method which we will see below). We already decided to use a HashMap, so let's begin this in Java by initializing our map, and variables and also include our return statements:
import java.util.HashMap;
class Solution {
public int mostFrequentEven(int[] nums) {
int appeared = 1;
int min_num = Integer.MAX_VALUE; //use max value because we will be updating
//this variable using less than and eventually return if a solution exists
HashMap<Integer, Integer> map = new HashMap<>();
if(map.size() == 0) return -1; //returns -1 if no nums in array are divisible by 2
return min_num; //else returns the min num
//if a num exists that is divisible by 2, min_num will be updated
}
}Now that we have all our objects initialized and our return statements set, we can get to the actual logic of the problem. We will have to use one for loop to look through the array and set the key-value pairs in our map object.
Now for the fun part. The logic will be as follows:
- Loop through the given array and check if each number is divisible by 2
- If so insert that number into the map as a key and set its value to 1
- Here we update our min_num variable by checking that this number has appeared at least once. Set min_num = whichever number is smaller; these being the current number we are checking and the current value of min_num which we set as the largest possible value in Java earlier(This can be a bit wonky sounding but as we implement this in code it should become a bit more clear)
- If the number has already appeared and been set into the map, then update its value by adding 1 and doing the same check in the last step. If the number is the same as our current minimum it should not change but say for example the number is larger and has appeared the same amount of times as the other number, we can then select the smaller of the two. This check helps us break that exact tie
- Finally, if a number that satisfies the requirement appears more than the current min_num, we set the min_num to the current number. (remember that we keep the “most amount of repetitions” in our appeared variable)
- This process will be repeated for every number in the array; if all goes well, we should have our solution!
This logic can sound a bit confusing but the implementation should help paint the full picture in your head. At the end of this tutorial, follow along with the full code implementation using a pen and paper with one of the example test cases to grasp the full understanding of how this works and how the variables get updated.
Here is the logic implemented:
for(int i = 0; i < nums.length; i++){
if(nums[i] % 2 == 0) { //checks if the remainder is equal to 0 when divided by 2
if(!map.containsKey(nums[i])) { //if map does not contain this number
map.put(nums[i], 1);
if(map.get(nums[i]) == appeared) {
min_num = Math.min(nums[i], min_num); //updates the min num
}
} else { //if the map does contain current number, skips to here
map.put(nums[i], map.get(nums[i]) + 1);
if(map.get(nums[i]) == appeared) { //updates how many times the number has appeared
min_num = Math.min(nums[i], min_num);
}
if(map.get(nums[i]) > appeared) { //checks if this number has appeared more than the current number
appeared = map.get(nums[i]);
min_num = nums[i];
}
}
}
}
Great! Now let's put it all together:
import java.util.HashMap;
class Solution {
public int mostFrequentEven(int[] nums) {
int appeared = 1;
int min_num = Integer.MAX_VALUE; //use max value because we will be updating
//this variable using less than and eventually return if a solution exists
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; i++){
if(nums[i] % 2 == 0) { //checks if the remainder is equal to 0 when divided by 2
if(!map.containsKey(nums[i])) { //if map does not contain this number
map.put(nums[i], 1);
if(map.get(nums[i]) == appeared) {
min_num = Math.min(nums[i], min_num); //updates the min num
}
} else { //if the map does contain current number, skips to here
map.put(nums[i], map.get(nums[i]) + 1);
if(map.get(nums[i]) == appeared) { //updates how many times the number has appeared
min_num = Math.min(nums[i], min_num);
}
if(map.get(nums[i]) > appeared) { //checks if this number has appeared more than the current number
appeared = map.get(nums[i]);
min_num = nums[i];
}
}
}
}
if(map.size() == 0) return -1; //returns -1 if no nums in array are divisible by 2
return min_num; //else returns the min num
//if a num exists that is divisible by 2, min_num will be updated
}
}Amazing! I hope you are now able to see how we used our HashMap to store keys and values in an attempt to find the most frequent even number. Once again, for a better understanding, run through this code with a pen and paper using an example test case and you may have an easier time grasping the concept. HashMaps are a convenient and powerful tool that can be applicable in a wide variety of cases. If you’re ever struggling to find ways to speed up your code don't forget to try throwing a HashMap at it.
I do hope whoever is reading this found this useful, for more of my ramblings like, follow, and comment. See you next time!
