grid47 Exploring patterns and algorithms
Aug 28, 2024
9 min read
Solution to LeetCode 705: Design HashSet Problem
Design a custom HashSet without using any built-in hash table libraries. Implement the MyHashSet class with methods to add, remove, and check the existence of a value.
Problem
Approach
Steps
Complexity
Input: You are given a set of operations to perform on a custom HashSet. The operations are: add, remove, and contains, each involving a key (an integer).
• At most 10^4 operations will be made on the HashSet.
Output: The function should return the results of the operations. If the operation is add or remove, return null. If the operation is contains, return a boolean value (true or false).
• Explanation: In this example, we first add 1 and 2 to the HashSet. We check if 1 is present (it is), then check for 3 (it isn't). Adding 2 again doesn't change the set, checking for 2 shows it is present, removing 2 removes it from the set, and checking for 2 afterward shows it isn't present.
Approach: We will design the HashSet using an array of linked lists to store the values. The key will be hashed to determine which linked list to check for the presence of the value.
Observations:
• The problem requires designing a set with efficient add, remove, and contains operations.
• The HashSet should ideally perform operations in constant time (O(1)) on average.
• We can use the modulo operator to map keys to an index in an array, and handle collisions using linked lists.
Steps:
• Step 1: Initialize an array with a fixed size (for example, 10,000), where each element is a pointer to a linked list.
• Step 2: To add a key, hash the key using modulo and check if the value already exists in the list at that index. If it doesn't exist, add it to the list.
• Step 3: To remove a key, find the key in the list and remove it.
• Step 4: To check if a key exists, hash the key and search through the list at the hashed index.
Empty Inputs:
• The set is initially empty, so we need to handle that scenario properly when performing operations.
Large Inputs:
• The HashSet should be efficient even with a large number of operations, so consider the size of the set and collisions.
Special Values:
• The key 0 is a valid input and should be handled correctly.
Constraints:
• Ensure that the HashSet can handle up to 10^6 keys and 10^4 operations efficiently.
// int val;
// ListNode* next;
// ListNode(int val, ListNode* nxt) {
// this->val = val
// this->next = nxt;
// }
// };
classMyHashSet {
public:int sz =10000;
vector<ListNode*> lst;
MyHashSet() {
lst.resize(sz, NULL);
}
voidadd(int key) {
int num = key%sz;
if(lst[num] ==NULL) {
lst[num] =new ListNode(key, NULL);
return;
}
ListNode* cur = lst[num], *prv =NULL;
while(cur) {
if(cur->val == key) return;
prv = cur;
cur = cur->next;
}
prv->next =new ListNode(key, NULL);
}
voidremove(int key) {
int num = key%sz;
if(lst[num] ==NULL) {
return;
}
if(lst[num]->val == key) {
auto it = lst[num];
lst[num] = lst[num]->next;
it->next =NULL;
return;
}
ListNode* cur = lst[num]->next, *prv = lst[num];
while(cur) {
if(cur->val == key) {
prv->next = cur->next;
cur->next =NULL;
return;
}
prv = cur;
cur = cur->next;
}
}
boolcontains(int key) {
int num = key%sz;
ListNode* cur = lst[num];
while(cur) {
if(cur->val == key) {
returntrue;
}
cur = cur->next;
}
returnfalse;
}
};
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet* obj = new MyHashSet();
* obj->add(key);
* obj->remove(key);
* bool param_3 = obj->contains(key);
1 : Class Definition
classMyHashSet {
Begin definition of the MyHashSet class.
2 : Access Specifier
public:
Public access section of the class.
3 : Variable Initialization
int sz =10000;
Initialize the size of the hash set to 10000.
4 : Data Structure Initialization
vector<ListNode*> lst;
Declare a vector of ListNode pointers to store the linked list chains.
5 : Constructor
MyHashSet() {
Constructor to initialize the hash set.
6 : Vector Resize
lst.resize(sz, NULL);
Resize the vector to hold 'sz' number of elements, initialized to NULL.
7 : Method Definition
voidadd(int key) {
Method to add a key to the hash set.
8 : Modular Arithmetic
int num = key%sz;
Calculate the index in the hash table using modulo operation.
9 : Condition Check
if(lst[num] ==NULL) {
Check if the list at the calculated index is empty.
10 : Memory Allocation
lst[num] =new ListNode(key, NULL);
Allocate a new ListNode and add it to the list at the calculated index.
11 : Return Statement
return;
Return if the key was added successfully.
12 : List Traversal
ListNode* cur = lst[num], *prv =NULL;
Initialize pointers to traverse the linked list at the calculated index.
13 : While Loop
while(cur) {
Iterate through the linked list at the calculated index.
14 : Condition Check
if(cur->val == key) return;
If the key already exists, return without adding it.
15 : Pointer Update
prv = cur;
Move the 'prv' pointer to the current node.
16 : Pointer Update
cur = cur->next;
Move the 'cur' pointer to the next node in the list.
17 : Node Insertion
prv->next =new ListNode(key, NULL);
Insert the new key at the end of the list.
18 : Method Definition
voidremove(int key) {
Method to remove a key from the hash set.
19 : Modular Arithmetic
int num = key%sz;
Calculate the index in the hash table using modulo operation.
20 : Condition Check
if(lst[num] ==NULL) {
Check if the list at the calculated index is empty.
21 : End If Condition
return;
Return if the list is empty, as the key cannot be removed.
22 : Remove Head Node
if(lst[num]->val == key) {
If the head node contains the key, remove it.
23 : Memory Deallocation
auto it = lst[num];
Temporary pointer to hold the node to be removed.
24 : Pointer Update
lst[num] = lst[num]->next;
Update the head of the list to the next node.
25 : Memory Deallocation
it->next =NULL;
Disconnect the removed node from the list.
26 : Return Statement
return;
Return after the node is removed.
27 : List Traversal
ListNode* cur = lst[num]->next, *prv = lst[num];
Initialize pointers to traverse the linked list at the calculated index.
28 : While Loop
while(cur) {
Iterate through the linked list to find the key.
29 : Condition Check
if(cur->val == key) {
If the key is found, remove it.
30 : Pointer Update
prv->next = cur->next;
Remove the key from the list by updating pointers.
31 : Memory Deallocation
cur->next =NULL;
Disconnect the node to be removed from the list.
32 : Return Statement
return;
Return after the key is removed.
33 : Pointer Update
prv = cur;
Move the 'prv' pointer to the current node.
34 : Pointer Update
cur = cur->next;
Move the 'cur' pointer to the next node.
35 : Method Definition
boolcontains(int key) {
Method to check if a key is present in the hash set.
36 : Modular Arithmetic
int num = key%sz;
Calculate the index in the hash table using modulo operation.
37 : List Traversal
ListNode* cur = lst[num];
Initialize a pointer to traverse the linked list at the calculated index.
38 : While Loop
while(cur) {
Iterate through the list to search for the key.
39 : Condition Check
if(cur->val == key) {
If the key is found, return true.
40 : Return Statement
returnfalse;
Return false if the key was not found.
Best Case: O(1), when the key is directly mapped to an index and there are no collisions.
Average Case: O(1), assuming that the hashing function distributes keys evenly and collisions are rare.
Worst Case: O(n), in the case of many collisions at a particular index in the array.
Description: The time complexity for each operation is O(1) on average, but can degrade to O(n) in the worst case due to hash collisions.
Best Case: O(m), where m is the size of the underlying array used for storing the keys.
Worst Case: O(n), where n is the number of elements stored in the set, as the space complexity depends on the number of keys inserted.
Description: The space complexity is linear with respect to the number of keys stored in the HashSet.
