Design HashSet | Optimized Solution | Daily Leetcode Challenge
\nclass MyHashSet {\nprivate:\n    // Define a vector to store buckets\n    vector<list<int>> buckets;\n    // Define the number of buckets (arbitrarily chosen,
```\nclass MyHashSet {\nprivate:\n    // Define a vector to store buckets\n    vector<list<int>> buckets;\n    // Define the number of buckets (arbitrarily chosen, you can optimize it)\n    int numBuckets = 1000;\n\n    // Hash function to determine the bucket index for a given key\n    int hash(int key) {\n        return key % numBuckets;\n    }\n\npublic:\n    MyHashSet() {\n        // Initialize the vector of buckets with empty lists\n        buckets.resize(numBuckets);\n    }\n    \n    // Insert the value key into the HashSet\n    void add(int key) {\n        int index = hash(key);\n        // Iterate over the bucket and check if the key already exists\n        for (int value : buckets[index]) {\n            if (value == key) {\n                // Key already exists, return\n                return;\n            }\n        }\n        // Key does not exist, add it to the bucket\n        buckets[index].push_back(key);\n    }\n    \n    // Returns whether the value key exists in the HashSet or not\n    bool contains(int key) {\n        int index = hash(key);\n        // Iterate over the bucket and check if the key exists\n        for (int value : buckets[index]) {\n            if (value == key) {\n                // Key exists, return true\n                return true;\n            }\n        }\n        // Key does not exist, return false\n        return false;\n    }\n    \n    // Removes the value key in the HashSet. If key does not exist, do nothing.\n    void remove(int key) {\n        int index = hash(key);\n        // Iterate over the bucket and check if the key exists\n        for (auto it = buckets[index].begin(); it != buckets[index].end(); ++it) {\n            if (*it == key) {\n                // Key exists, remove it from the bucket\n                buckets[index].erase(it);\n                // Key found and removed, return\n                return;\n            }\n        }\n    }\n};\n```\n\n**Explanation:**\n\n* The MyHashSet class is implemented using separate chaining as the collision resolution strategy.\n* The class uses a vector of lists (buckets) to store the values. Each bucket represents a unique hash value.\n* The numBuckets variable determines the number of buckets. You can adjust this value based on the expected number of elements and the desired trade-off between memory usage and lookup performance. In this implementation, it is set to 1000 arbitrarily.\n* The hash function calculates the bucket index for a given key by performing the modulo operation on the key with the number of buckets.\n* The add function adds the key to the corresponding bucket only if it doesn\'t already exist in the bucket. It does this by iterating over the bucket and comparing each value with the key. If a match is found, the function returns without adding the key.\n* The contains function checks if the key exists in the corresponding bucket by iterating over the bucket and comparing each value with the key. If a match is found, the function returns true. If the iteration completes without finding a match, the function returns false.\n* The remove function removes the key from the corresponding bucket if it exists. It does this by iterating over the bucket, comparing each value with the key, and erasing the matching value from the bucket.\n\n**Complexity Analysis**\n\nTime Complexity:\n* Adding an element (add operation): O(1) on average, O(n) in the worst case.\n* Checking if an element exists (contains operation): O(1) on average, O(n) in the worst case.\n* Removing an element (remove operation): O(1) on average, O(n) in the worst case.\n\nSpace Complexity: O(1) on average, O(n) in the worst case.\n\nIn summary, the average time complexity for each operation (add, contains, remove) is constant time O(1), and the space complexity is constant O(1). However, in the worst case scenario where all elements are stored in a single bucket, the time complexity becomes linear O(n), and the space complexity becomes O(n), where n is the number of elements in the hash set.\n\n**PLEASE UPVOTE :)**
['C']