Sponsored
Sponsored
The direct address table approach is simple and efficient for this problem since the maximum key size is limited to 106. We can use a boolean array of size 106+1 where each index represents a key. The value stored at a given index indicates whether the key is present in the HashSet. This allows for O(1) time complexity for the 'add', 'remove', and 'contains' operations.
Time Complexity: O(1) for all operations (add, remove, contains).
Space Complexity: O(MAX), which is O(10^6).
1class MyHashSet:
2 def __init__(self):
3 self.container = [False] * 1000001
4
5 def add(self, key: int) -> None:
6 self.container[key] = True
7
8 def remove(self, key: int) -> None:
9 self.container[key] = False
10
11 def contains(self, key: int) -> bool:
12 return self.container[key]
13In Python, we make use of a list (an array-like structure) initialized with False values. The add, remove, and contains functions manipulate or query this list.
This approach simulates a hash set using a hash function to assign keys to buckets, dealing with potential collisions using chaining. We create an array of lists, where each list contains keys that hash to the same index. This way, operations require traversing these short lists upon collisions.
Time Complexity: O(1) average, O(n) worst-case for add, remove, and contains due to collision chains.
Space Complexity: O(n), where n is the number of keys actually added.
1
In C, we use an array of linked lists to manage collisions. A fixed-size hash-table ('BASE') is initialized, and the hash function determines which index (or 'bucket') a key belongs to. We handle collisions by adding new keys to the list at each bucket. The remove function deletes a node by updating links, and contains searches the linked list to find a key.