Design HashSet
To solve this problem, we could design our own simple hash function and use a boolean array to store keys.
Initialize a large boolean array of size 10^6 + 1 (as per the constraint). This array will act as our hash table where the index will be used as the key.
For
add(key)
, simply set the value at the index equal tokey
in our array to true.For
contains(key)
, return the value at the index equal tokey
in our array.For
remove(key)
, set the value at the index equal tokey
in our array to false.
Here’s an example of how we could implement this in Java:


In the above solution:
 Our hash function is basically an identity function where the key is mapped to itself.
 The time complexity of
add
,remove
, andcontains
operations is O(1) because we are directly accessing the index in our array.  The space complexity is O(N) where N is the size of the array (which is based on the maximum possible key value).
This solution is quite efficient but it has one limitation that the maximum possible key value is hardcoded. It might not be a good approach if the maximum key value is not known in advance or if it can change dynamically.
Based on constraints, this solution should work.
Python solution:


In this Python implementation:
self.set
is a list that acts as our hash table. The
add
method sets the corresponding index to True, indicating that the key exists in the hash set.  The
remove
method sets the corresponding index to False, indicating that the key has been removed from the hash set.  The
contains
method returns the value at the corresponding index, which will be True if the key exists in the hash set and False otherwise.
Again, as with the Java implementation, the time complexity for the add
, remove
, and contains
operations is O(1), and the space complexity is O(N) where N is the size of self.set
.
Identifying Problem Isomorphism
“Design HashSet” can be related to “Jewels and Stones”. While not exactly isomorphic, they share some common themes.
“Design HashSet” requires you to implement a HashSet without using any builtin hash set libraries. This problem is about creating a data structure that can efficiently add, remove, and contain elements.
“Jewels and Stones” involves finding how many stones you have that are also jewels. This problem can be solved efficiently using a HashSet to store the jewels and then iterate through the stones to check how many are also jewels.
“Jewels and Stones” is simpler as it mostly involves using an existing data structure (HashSet) to solve a problem, whereas “Design HashSet” involves creating a new data structure from scratch. If you understand the concept of a HashSet and how it’s used in the “Jewels and Stones” problem, it can give you a solid foundation for designing your own HashSet in the more complex problem.
10 Prerequisite LeetCode Problems
“Design HashSet” involves designing a data structure, hashset, in this case. Understand how data structures work, especially hash based structures. Here are 10 problems for preparation:
155. Min Stack: To understand the concept of designing a data structure.
232. Implement Queue using Stacks: To learn how to use one data structure to implement another.
225. Implement Stack using Queues: The reverse of the above problem.
706. Design HashMap: This problem will help you to understand the concept of designing a hashmap which is similar to a hashset.
208. Implement Trie (Prefix Tree): To understand how to design and implement a Trie, which can be a useful data structure.
303. Range Sum Query  Immutable: The problem involves designing a data structure to support certain types of queries, which will help you understand the design of data structures for specific tasks.
1710. Maximum Units on a Truck: This problem will help you understand how to work with objects and their properties, similar to how a HashSet works with keys.
1365. How Many Numbers Are Smaller Than the Current Number: Helps in understanding how data can be structured for efficient querying, which is also important in a HashSet.
242. Valid Anagram: This problem will give you good practice of using hashing.
202. Happy Number: This problem involves using a HashSet to track previously seen numbers and helps understand how a HashSet works.
These cover how to design data structures and how they can be used to solve specific problems effectively.


Problem Classification
This problem falls under the domain Data Structures and Algorithms. The task here involves creating a custom implementation of a HashSet, a fundamental data structure.
‘What’ Components:
 Input: There are no direct inputs to the class. Instead, the class should be able to process a series of operations, namely
add
,contains
, andremove
. These operations are called with an integer key.  Output: Depending on the method called, the class does different things.
add
andremove
don’t need to return anything, butcontains
should return a boolean indicating whether a given key is present in the HashSet or not.  Constraints: The class should implement a HashSet without using any builtin hash table libraries.
This is a Data Structure Design Problem. The task is to design and implement a custom HashSet, providing methods for adding elements, checking if an element is present, and removing elements. This problem highlights the importance of understanding how basic data structures like HashSets work under the hood and how to recreate them.
Language Agnostic Coding Drills
 Dissect the code and identify each distinct concept it contains:
Concept 1: Defining a Class in Python  The creation of a new object type, here the
MyHashSet
class.Concept 2: Object Initialization  The
__init__
method is used to initialize an instance of the class, here setting up a defaultdict as the internal storage for the set.Concept 3: Function Definitions inside a class  The
add
,remove
, andcontains
methods are defined inside the class, modifying or interacting with the internal state of class instances.Concept 4: Use of defaultdict  A defaultdict is used as the primary data structure for the class. This type of dictionary returns a default value when accessed with a key that doesn’t exist in the dictionary.
Concept 5: Keyvalue manipulation in defaultdict  The addition, removal, and checking of values in the defaultdict.
 List out these coding concepts or drills in order of increasing difficulty:
Concept 1  Defining a Class in Python (Beginner): This is a basic concept in ObjectOriented Programming which most programming languages employ.
Concept 2  Object Initialization (Beginner): This is also a basic concept where the programmer learns to initialize object instances.
Concept 3  Function Definitions inside a class (Intermediate): These methods interact with the internal state of the object, which adds some complexity.
Concept 4  Use of defaultdict (Intermediate): Understanding defaultdict and its differences from a standard dictionary require a good understanding of Python’s data structures.
Concept 5  Keyvalue manipulation in defaultdict (Intermediate): This requires understanding how defaultdicts work, and how to manipulate their contents.
 Problemsolving approach that would lead from the problem statement to the final solution:
The overall approach to this problem is to mimic the functionality of a HashSet using a Python defaultdict. Here’s the stepbystep process:
Understand the basic functionalities that a HashSet provides  adding an element, removing an element, and checking if an element exists.
Implement the class
MyHashSet
that will have these methods. Initialize the class with a defaultdict, which will serve as the internal data storage.Implement the
add
method. This should set the value of the provided key in the defaultdict toTrue
.Implement the
remove
method. This should set the value of the provided key in the defaultdict toFalse
.Implement the
contains
method. This should return the value of the provided key in the defaultdict. Due to the nature of defaultdict, if the key doesn’t exist, it will return the default value,False
, indicating that the key is not in the set.
Each of these steps corresponds to a separate coding drill. When these drills are combined in the order outlined above, they solve the overall problem.
Targeted Drills in Python
 Pythonbased coding drills for each identified concept:
Concept 1  Defining a Class in Python
1 2
class MyClass: pass
Concept 2  Object Initialization
1 2 3
class MyClass: def __init__(self): self.my_var = "Hello, World!"
Concept 3  Function Definitions inside a class
1 2 3 4 5 6
class MyClass: def __init__(self): self.my_var = "Hello, World!" def print_var(self): print(self.my_var)
Concept 4  Use of defaultdict
1 2 3
from collections import defaultdict my_default_dict = defaultdict(int) # This will return 0 for any key that does not exist.
Concept 5  Keyvalue manipulation in defaultdict
1 2 3 4 5
from collections import defaultdict my_default_dict = defaultdict(int) my_default_dict["my_key"] = 1 # Set value print(my_default_dict["my_key"]) # Get value
 Problemspecific concepts:
Concept 6  Simulating a HashSet with a defaultdict
1 2 3 4 5 6 7 8 9 10 11 12 13 14
from collections import defaultdict class MyHashSet: def __init__(self): self.set = defaultdict(int) def add(self, key): self.set[key] = True def remove(self, key): self.set[key] = False def contains(self, key): return self.set[key]
This drill is essential for our problem because it provides the structure and logic of our
MyHashSet
class, which directly simulates a HashSet using a defaultdict.
 Integration of pieces to solve the initial problem:
Start by understanding the basic principles of objectoriented programming in Python, including class definition, object initialization, and method definition inside a class (Concepts 13).
Once you have a basic understanding of how classes work in Python, start to understand defaultdict, a specialized dictionary provided by Python that returns default values for nonexisting keys (Concept 4).
With knowledge of defaultdict, you should understand how to manipulate its keyvalue pairs, including how to add a pair, remove a pair, and check the value of a key (Concept 5).
With all the above knowledge, you should understand and be able to implement the
MyHashSet
class, which uses a defaultdict to simulate the behavior of a HashSet (Concept 6).
In the final step, we combine all the above concepts to create the solution for our problem: a MyHashSet
class with methods for adding a key, removing a key, and checking if a key exists.