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.

Link: https://leetcode.com/problems/design-hashset/description/

Problem Explanation with examples:-

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<sup>6</sup>

• At most 10<sup>4</sup> calls will be made to add, remove, and contains.

Intuition:-

• Keep a dictionary or HashMap to store the keys with 1 as true value to depict that the key is present in the set.

• When add is called, simply add the key to the dictionary with value as 1 and when remove is called, simply add the key to the dictionary with value as 0.

• When contains is called, simply check if the key is present in the dictionary and return true if the value is 1 and false if the value is 0 or the key is not present in the dictionary.

Solution:-

• Initialize a dictionary or HashMap mp to store the keys.

• Add the key to the dictionary with value as 1 when add is called.

• Add or overwrite the key to the dictionary with value as 0 when remove is called.

• Return true if the key value in map is 1 and false if the key value in map is 0 or the key is not present in the map when contains is called.

Code:-

JAVA Solution

class MyHashSet {
    private Map<Integer, Integer> mp;

    public MyHashSet() {
        mp = new HashMap<>();
    }

    public void add(int key) {
        mp.put(key, 1);
    }

    public void remove(int key) {
        mp.remove(key);
    }

    public boolean contains(int key) {
        return mp.containsKey(key) && mp.get(key) == 1;
    }
}

Python Solution

class MyHashSet:

    def __init__(self):
        self.mp = {}

    def add(self, key: int) -> None:
        self.mp[key] = 1

    def remove(self, key: int) -> None:
        self.mp[key] = 0

    def contains(self, key: int) -> bool:
        return self.mp.get(key,-1) == 1

Complexity Analysis:-

TIME:-

The time complexity is O(1) for all operations.

SPACE:-

The space complexity is O(n) where n is the number of unique keys in the set.

References:-

• Dictionary

Connect with me:-

• Twitter

• Github

• LinkedIn