Leetcode 705. Design HashSet

Problem

Leetcode 705 - Design HashSet

Example:

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)

Approach

Since the question’s constraint is that $0 \leq key \leq 10^6$, we can initialize the array with size of $10^6$ with [False], then we once we add a key, we can just turn that index into True, and we don’t have to worry about adding the duplicate since turning True to True will still be True. For Remove, we do the same as Add except we turn that index into False. When we want to return that key, we can return that index.

Here is the Python code for the solution:

class MyHashSet:
    def __init__(self):
        self.arr = [False] * 1000001
    
    def add(self, key: int) -> None:
        self.arr[key] = True
    
    def remove(self, key: int) -> None:
        self.arr[key] = False
    
    def contains(self, key: int) -> bool:
        return self.arr[key]

Time Complexity and Space Complexity

Time Complexity: $O(1)$ for each operation since we’re just accessing the array

Space Complexity: $O(10^6)$ since we’re using array that is size of $10^6$