705. Design HashSet

Problem statement

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

Implement MyHashSet class:

• void add(key) Inserts the value key into the HashSet.

• bool contains(key) Returns whether the value key exists in the HashSet or not.

• void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

Example 1

Input
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1);      // set = [1]
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)

Constraints

• 0 <= key <= 10^6.

• At most 10^4 calls will be made to add, remove, and contains.

Solution 1: Store the keys

The simplest way is using a container to store the keys so you can identify if a key belongs to the HashSet or not.

Code

#include <iostream>
#include <vector>
using namespace std;
class MyHashSet {
    vector<int> _v;
public:
    MyHashSet() {        
    }   
    void add(int key) {
        if (!contains(key)) {
            _v.push_back(key);
        }
    }    
    void remove(int key) {
        auto it = _v.begin();
        while (it != _v.end()) {
            if (*it == key) {
                _v.erase(it);
                return;
            } else {
                it++;
            }
        }
    }    
    bool contains(int key) {
        for (int a : _v) {
            if (a == key) {
                return true;
            }
        }
        return false;
    }
};
int main() {
    MyHashSet m;
    m.add(1);
    m.add(2);
    cout << m.contains(1) << endl;
    cout << m.contains(3) << endl;
    m.add(2);
    cout << m.contains(2) << endl;
    m.remove(2);
    cout << m.contains(2) << endl;
}

Output:
1
0
1
0

Complexity

• Runtime: O(N) for all methods, where N is the number of values in the HashSet.

• Extra space: O(N).

Solution 2: Marking the keys

In this problem, the HashSet does not have anything other than methods add, remove and contains, which only check whether a key exists in it or not.

With this purpose you can simply mark the keys without storing them.

Code

#include <iostream>
#include <vector>
using namespace std;
class MyHashSet {
    vector<bool> _v;
public:
    MyHashSet() : _v(1000001, false){        
    }   
    void add(int key) {
        _v[key] = true;
    }    
    void remove(int key) {
        _v[key] = false;
    }    
    bool contains(int key) {
        return _v[key];
    }
};
int main() {
    MyHashSet m;
    m.add(1);
    m.add(2);
    cout << m.contains(1) << endl;
    cout << m.contains(3) << endl;
    m.add(2);
    cout << m.contains(2) << endl;
    m.remove(2);
    cout << m.contains(2) << endl;
}

Output:
1
0
1
0

Complexity

• Runtime: O(1).

• Extra space: O(1).

References

• https://leetcode.com/problems/design-hashset/

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.