When I first began coding, one of the fundamental concepts that I learned was arrays. I learned various techniques for manipulating arrays, such as iteration, adding or removing elements, and accessing values using their respective indices. During my technical interview studies, I encountered hash tables for the first time and was curious as to why they were such an important data structure. Honestly, at first, I was frustrated to learn about another unfamiliar topic. I thought arrays were the end-all-be-all only to discover hash tables, this weird data structure that is basically a dynamic array of linked lists. As I delved deeper into the concept, I gradually realized the immense power of this data structure. I discovered how the hash table could be used to optimize code, especially when it comes to looking up, inserting, or deleting data. This article aims to help beginners overcome their fear of hash tables and empower them to use this data structure efficiently during technical interviews.
Let's start by defining a hash table. A hash table is a data structure that stores key/value pairs efficiently. Different programming languages have different ways to implement hash tables. For example, in JavaScript, you can implement hash tables using an object, a Map object, or even a custom class. You may wonder what the difference is between using a simple object and a Map object when implementing hash tables. The main differences are as follows:
- A Map object has an inherited size property, whereas a simple object does not.
const sizeExample = new Map();
sizeExample.set("exampleOne", "1234");
sizeExample.set("exampleTwo", "5678");
console.log(sizeExample.size); // 2
- When using an object, default properties inherited from the Object class can be accidentally overwritten. However, using the Map object would not allow you to assign keys to inherited properties.
const obj = {};
obj.location = "Texas";
obj.hasOwnProperty = true
// Error: obj.hasOwnProperty is not a function
console.log(obj.hasOwnProperty("Texas"));
// hasOwnProperty() method allows you to check if a property
// is not inherited.
// if obj.hasOwnProperty was not assigned the value of true then the
// console.log statement would have returned true
- Finally, a Map object requires the use of set() and get() methods to assign and retrieve key-value pairs.
const cars = new Map();
cars.set("Vehicle", "Honda");
cars.set("Model", "Civic");
console.log(collection.get("Vehicle")); // Honda
console.log(collection.get("Model")); // Civic
Let's solve a coding problem now that you have a fundamental understanding of hash tables.
Question
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < na,b,c, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
The initial solution that may come to mind is using four nested loops to traverse and compare values within the array.
var fourSum = function(nums, target) {
n=nums.length;
final=[]
nums=nums.sort((a,b)=>a-b)
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
for(k=j+1;k<n;k++){
for(l=k+1;l<n;l++){
if(nums[i]+nums[j]+nums[k]+nums[l]==target){
final.push([nums[i],nums[j],nums[k],nums[l]])
}
while(nums[l+1]==nums[l]){
l++;
}
}
while(nums[k+1]==nums[k]){
k++;
}
}
while(nums[j+1]==nums[j]){
j++;
}
}
while(nums[i+1]==nums[i]){
i++;
}
}
return(final)
};
The current solution solves the problem, but its time complexity of O(n^4) is less efficient than using a hash table. Let's put the hash table to work and show its magic!
Let's start by understanding the problem we need to solve. Our task is to find all quadruplets in an array that add up to a target sum. The solution should return a two-dimensional array containing these quadruplets in no particular order. Importantly, none of the quadruplets should have identical values. Let's analyze the solution posted below in detail. I will break it down piece by piece to make it easier to understand.
var fourSum = function(nums, target) {
allPairedNums = {};
quadruplets = []
allNumbersTheSame = true
for(let x = 0; x < nums.length - 1; x++){
if (nums[x] !== nums[x+1]){
allNumbersTheSame = false
}
for(let y = x + 1; y < nums.length; y++){
currentSum = nums[x] + nums[y]
difference = target - currentSum
if(allPairedNums[difference]){
allPairedNums[difference].forEach(pair => {
quadruplets.push([pair[0], pair[1], nums[x], nums[y]])
})
}
}
for (let z = 0; z < x; z++){
currentSum = nums[z] + nums[x]
if(allPairedNums[currentSum]){
allPairedNums[currentSum].push([nums[z], nums[x]])
} else {
allPairedNums[currentSum] = [[nums[z], nums[x]]]
}
}
}
if (allNumbersTheSame){
return quadruplets.slice(quadruplets.length - 1)
}else {
return quadruplets
}
};
You will first notice the three variables listed in this function:
allPairedNums = {};
quadruplets = []
allNumbersTheSame = true
The "allPairedNums" object is a hash table that stores all pairs from the given array. Each item in the hash table has a key, which is the sum of the two numbers in the pair, and a value that contains an array with those two numbers. If there are multiple pairs whose sum is the same, they will be grouped together under the same key in a two-dimensional array.
//Array
[1,0,-1,0,-2,2]
//Possible Pairs
all pairs {
'0': [ [ 1, -1 ], [ 0, 0 ] ],
'1': [ [ 1, 0 ], [ 1, 0 ] ],
'-1': [ [ 0, -1 ], [ -1, 0 ], [ 1, -2 ] ],
'-2': [ [ 0, -2 ], [ 0, -2 ] ],
'-3': [ [ -1, -2 ] ]
}
The array "quadruplets" stores all found quadruplets in the given array.
[[1,0,-1,0],[1,-1,-2,2],[0,0,-2,2]]
The boolean variable "allNumbersTheSame" is used to determine if all the numbers in the array are the same. If they are, then the slice method will be applied to the array to ensure only one pair is returned.
The first for loop iterates over the entire array, and the if statement compares each value to the next one to check whether they are the same or not. If the elements in the array have different values, the boolean variable "allNumbersTheSame" is set to false. This indicates that multiple arrays can be added to the two-dimensional array.
for(let x = 0; x < nums.length - 1; x++){
if (nums[x] !== nums[x+1]){
allNumbersTheSame = false
}
...
Next, taking a look at the first nested for loop we compare the current element to the rest of the elements in the array. To achieve the target sum, we add the two given elements and subtract the result from the target sum. This operation is performed because we understand that the total of the two remaining elements must be equal to the difference between the target sum and the sum of the first two elements. Please have a look at the pseudocode provided below for better understanding.
// pseudocode
target = a + b + c + d
currentSum = a + b
c + d = targetSum - currentSum
//example
16 = 5 + 5 + 4 + 2
10 = 5 + 5
4 + 2 = 16 - 10
//for loop
for(let x = 0; x < array.length - 1; x++){
for(let y = x + 1; y < array.length; y++){
currentSum = array[x] + array[y]
difference = target - currentSum
...
After obtaining the difference between the target sum and the pair, we proceed to search the hash table for a matching key. If we find a matching key, we add each quadruplet to the quadruplets array. We use the forEach method to ensure that we add all the possible quadruplets to the array since a key in the hash table can contain multiple pairs.
if(allPairedNums[difference]){
allPairedNums[difference].forEach(pair => {
quadruplets.push([pair[0], pair[1], array[x], array[y]])
})
}
//
//target = 16
16 = 5 + 5 + 4 + 2
//currentSum = 10
10 = 5 + 5
//difference = 6
4 + 2 = 16 - 10
//Does the hash table contain a key of 6 ?
-> '6': [[3,3][4,2]]
//Add each quadruplet to the array
[[3,3,5,5][4,2,5,5]]
...
You might be wondering why we waited until the end to add each pair to the "allPairedNums" hash table. The reason for this is to make sure we do not add duplicate quadruplets to the array. If we add each pair to the hash table before performing the operations explained earlier, then we could end up having two pairs that sum to the same value with the same numbers, just in a different order. Take a look at the example below.
//Hash table with a key of 6
'6': [[2,4][4,2]]
As you can see, we have two pairs of numbers that are the same, just in a different order. Therefore, if we were to add a pair of numbers to each array, the resulting quadruplets would be identical.
//current sum added to each array is [4,5]
[[2,4,4,5][4,2,4,5]]
The following for loop adds the current sum to the hash table.
for (let z = 0; z < x; z++){
currentSum = nums[z] + nums[x]
if(allPairedNums[currentSum]){
allPairedNums[currentSum].push([nums[z], nums[x]])
} else {
allPairedNums[currentSum] = [[nums[z], nums[x]]]
}
}
If the current sum is already a key in the hash table, the pair will be added as a new array to the two-dimensional array. If the current sum is not found, a new key/value pair will be created. The current sum will be the key, and the paired numbers will be the value in the new two-dimensional array.
After adding all the quadruplets to the quadruplets array, we will verify whether all the elements in the nums array are identical or not. If they are, we will use the slice method to obtain a two-dimensional array containing only one quadruplet. If not, a two-dimensional array will be returned containing multiple quadruplets.
if (allNumbersTheSame){
return quadruplets.slice(quadruplets.length - 1)
}else {
return quadruplets
}
Great Job!! 🎉
You have now successfully generated an array with all possible quadruplets, avoiding any duplicates. Although the function may have seemed complex, the key takeaway is that hash tables simplify finding values. Instead of relying on indices to locate values in an array, unique keys can be used for faster lookup. This solution boasts an impressive O(n^2) time complexity, making it much faster than the original solution. I hope this article helped alleviate any concerns you may have had regarding the use of hash tables. Additionally, I want to express my gratitude to Clement Mihailescu and the AlgoExpert team for their program, which helped me gain a better understanding of fundamental concepts in data structures and algorithms. Until next time!