# 705. Design HashSet

Check out the problem statement here

Approach 1:

We use a 1D array to add the elements , if it doesn’t contain one already. The remove operation searches this array whether the element is in the array. If yes, then we remove it. The contains operation searches for the element whether it is present in the array or not.

class MyHashSet:def __init__(self):

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

if(key not in self.array):

self.array.append(key)def remove(self, key: int) -> None:

if(key in self.array):

for i in range(len(self.array)):

if(self.array[i]==key):

if(i==len(self.array)-1):

self.array=self.array[:i]

else:

self.array=self.array[:i]+self.array[i+1:]

break

else:

return(None)def contains(self, key: int) -> bool:

if(key in self.array):

return True

return False# Your MyHashSet object will be instantiated and called as such:

# obj = MyHashSet()

# obj.add(key)

# obj.remove(key)

# param_3 = obj.contains(key)

Time : O(no.of times the functions are called * the iteration of the array for the certain operation)

Space:O(max number of elements in the array at a time)

Approach 3:

Using the fundamentals of hashing and hashing function. For a hashmap the load factor LF should be around 0.75.This ensures O(1) lookups.

LF= number of items to insert in to hash table/ number of bucket(size of hash table)

If it crosses beyond this ratio. Then we increase(double) the size of hash table(number of buckets).

We choose LF around 0.66 here.

class MyHashSet:

def __init__(self):

#number of buckets

#The load factor of the hash table should not cross 0.75

# Here the load factor is

# LF= number of entries / number of buckets

# 10^4/15000 = 0.666

self.buckets=15000

self.hashtable=[[] for i in range(self.buckets)]

def hash_function(self,key):

return(key%self.buckets)

def add(self, key: int) -> None:

index = self.hash_function(key)

if(key not in self.hashtable[index]):

self.hashtable[index].append(key)

def remove(self, key: int) -> None:

index = self.hash_function(key)

if(key in self.hashtable[index]):

self.hashtable[index].remove(key)def contains(self, key: int) -> bool:

index = self.hash_function(key)

if(key in self.hashtable[index]):

return(True)

return(False)

Time : O(1)

This time complexity is the time complexity for executing each of the add , remove or contains function. The final time complexity is actually , linearly dependent on the number of times the functions are called on the MyhashSet object created so far.

Space: O(max number of elements in the hash table at a time + number of buckets )

Approach 3:

This can also be done without using concept of hashing, but still gives the O(1) Time complexity.

`class MyHashSet:`

def __init__(self):

self.arr= [False] * (10**6 +1)

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 : O(1)

Space: O(Maximum value of the item to be inserted), here it is 10⁶

In terms of space, it is the least efficient solution .