HashMaps
HashMaps are part of the Java collections framework, hashmaps are an unordered collection of data which means that when inserted, the order in which it was inserted doesn’t stay ordered like an ArrayList or LinkedList. HashMaps stores values as Key-value pairs and the keys & values could be of different combinations of strings, doubles, integers, etc. Some important methods for hashmaps are put(), containsKey(), containsValue(), get(), size(), remove(), and clear().
Put function takes 2 parameters which are parameter 1 = key and parameter 2 = value and adds a new entry to the hashmap. Get function takes 1 parameter which is the key and returns the value associated with the key in the hashmap. The containsKey function takes a parameter of the key in the key-value pair and returns a boolean value of true or false based on if the hashmap contains a key equal to the parameter.
The Two-Sum Problem
The problem is to return the two indices in an integer array whose integer values are equal to the int target
An example for an integer array: arr=[1,2,3,4] and target=7, the result for this example would be [2,3] which are the indices locations that are equal to 7 since arr[2] + arr[3] = 7 which is 3+4 = 7
Brute Force solution to Two-Sum
To brute force your way to the answer for the two-sum problem you would create 2 for-loops that are nested. The first for-loop iterates through the array starting from 0 to array length-1. The second for-loop iterates through the same array starting from 1 because you want to add the current array value from the nested for-loop to the current outer loop’s array value and see if it equals to target with Arr[j] + arr[k] == target. Then when the if statement holds true you record the indices by inserting them to an array like such result[0] = j; result[1] = k; and lastly you return the result array to finally solve the problem through brute force.
Now the time complexity of this problem is O(n²) because having a nested for-loop means O(n) * O(n) since both for loops are O(n) therefore it equals O(n²).
class BruteForceSolution{
public int[] twoSum(int [] arr, int target){
int result [] = new int[2]; for(int j = 0; j < arr.length-1; j++){
for(int k = 1; k < arr.length; k++){
if(arr[j] + arr[k] == target){
result[0] = j;
result[1] = k;
return result;
}
}
} return result;
}
}
Hash Map solution to Two-Sum
Now to solve this problem with a hashmap with better time complexity of O(n). When using the hashmap we will first insert the first value of the example array with the put() function. Its key will be the value in the array and its value for the key-value pair is the indices in the array.
Now we will iterate through the array for O(n) and for each iteration will record (target-arr[i]) to an integer and use an if-statement to check if the hashmap contains that key and if it does that means we found our target and can record the indices and return the result of the indices or else add the array value as a key and its array index as a value into the hashmap and continue iterating until we find a pair that matches the if edge case.
class HashMapSolution(){
public int[] twoSum(int[] arr, int target){
int [] result = new int[2];
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
// insert the first value in arr[] and its index of zero
hm.put(arr[0], 0); for(int i = 1; i < arr.length; i++){
// get the value that when arr[i] + pairToArrayValue will get the target
int pairToArrayValue = target - arr[i];
// check if hashmap contains a key equal to the pair value
if(hm.containsKey(pairToArrayValue)){
result[0] = hm.get(pairToArrayValue); // returns the index of that value
result[1] = i;
return result;
}
else{
map.put(arr[i], i); // add new key-value for array value and its index
}
}
return result;
}
}
In conclusion, we figured out what a HashMap is and some of its core functions and showed how it can optimize a problem to improve the time needed to solve it.
