algoadvance

Leetcode 705. Design HashSet

Problem Statement

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class:

• void add(int key): Inserts the value key into the HashSet.
• bool contains(int key): Returns whether the value key exists in the HashSet or not.
• void remove(int key): Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

Clarifying Questions

1. What is the range of the key values that we need to handle?
   • Answer: We can assume keys are non-negative integers in the range [0, 10^6).
2. Is it necessary to ensure that the operations are time efficient?
   • Answer: Yes, the operations should ideally be O(1) on average.

Strategy

We’ll use a combination of a hash table with chaining to handle collisions and an array to store the values. Here is the strategy:

1. Hash Function: We’ll design a simple hash function using modulo operation.
2. Buckets: Use an array of linked lists (or similar structure) for the hashing, with each index in the array representing a bucket.
3. Handling Collisions: When a collision occurs (two keys hashing to the same index), we will handle it by chaining nodes in a linked list at that index.

Code

#include <vector>
#include <list>

class MyHashSet {
private:
    static const int BUCKET_SIZE = 769;  // A prime number bucket size
    std::vector<std::list<int>> buckets;
    
    int hash(int key) {
        return key % BUCKET_SIZE;
    }

public:
    MyHashSet() {
        buckets.resize(BUCKET_SIZE);
    }
    
    void add(int key) {
        int bucket_idx = hash(key);
        auto &bucket = buckets[bucket_idx];
        for (int el : bucket) {
            if (el == key) return;  // Key already exists
        }
        bucket.push_back(key);
    }
    
    bool contains(int key) {
        int bucket_idx = hash(key);
        auto &bucket = buckets[bucket_idx];
        for (int el : bucket) {
            if (el == key) return true;
        }
        return false;
    }
    
    void remove(int key) {
        int bucket_idx = hash(key);
        auto &bucket = buckets[bucket_idx];
        bucket.remove(key);  // Removes the first occurrence of key
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * bool param_2 = obj->contains(key);
 * obj->remove(key);
 */

Time Complexity

• add(key): O(1) on average. This is because the average length of the bucket is constant, assuming a good distribution of keys.
• contains(key): O(1) on average. Same reasoning as above.
• remove(key): O(1) on average. Again, this holds if our hash function distributes keys well.

Space Complexity

• Space Complexity: O(N + B)
  • N is the number of unique keys added.
  • B is the bucket size, which is a constant (769 in our case).

This approach effectively balances the need for simplicity and efficiency, ensuring that operations remain performant across a wide range of expected inputs.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?