705. Design HashSet

EasyDesignArrayHash TableLinked ListHash Function

Problem Description

The task is to design a data structure MyHashSet that simulates the behavior of a set without using any built-in hash table libraries. A hash set is a collection of unique elements. The MyHashSet class should support three operations:

add(key): Inserts the value key into the HashSet.
contains(key): Returns true if the key exists in the HashSet and false otherwise.
remove(key): Removes the key from the HashSet. If the key does not exist, no action should be taken.

The challenge is to implement these functionalities manually, ensuring that the operations are as efficient as possible.

Intuition

To implement a HashSet, we can use an array where the indices represent the potential keys and the values at those indices represent whether the key is present in the set or not. Given the constraints, we can assume the set will only need to handle non-negative integer keys.

Here's the approach we can take:

Initialize: We create a large enough array to accommodate all possible keys. In this case, we initialize a Boolean array of size 1000001 (since the possible key range is from 0 to 1000000) and set all values to False indicating that initially, no keys are present in the HashSet.
Add: To add a key, we simply set the value at the index corresponding to the key in the array to True.
Remove: To remove a key, we set the value at the index corresponding to the key in the array back to False.
Contains: To check if a key is in the set, we return the value at the index corresponding to the key in the array, which is True if the key is present and False otherwise.

This approach is very direct and efficient, with all operations having a constant time complexity of O(1), which means the operation time does not depend on the size of the data in the HashSet.

Learn more about Linked List patterns.

Solution Approach

The solution involves three key steps that correspond to the three methods of the MyHashSet class: add, remove, and contains. Here’s how each method is implemented:

Initialization (__init__ method): The solution begins by initializing an array (or list in Python) named data to have a size of 1000001. This size is selected to ensure that any key within the expected range (0 to 1000000) can be directly mapped to an index of this array. Each element in the data array initially holds the value False, indicating that no keys are present in the HashSet to begin with.
```
def __init__(self):
    self.data = [False] * 1000001
```
Adding a Key (add method): Adding a key simply involves updating the value at the index equal to the key to True. This operation designates that the key is now present within the HashSet.
```
def add(self, key: int) -> None:
    self.data[key] = True
```
Removing a Key (remove method): To remove a key, the solution sets the index equal to the key back to False. This signifies that the key is no longer within the HashSet. If the key doesn't exist, this operation still sets the value to False, which has no effect as the value is already False.
```
def remove(self, key: int) -> None:
    self.data[key] = False
```
Checking Existence of a Key (contains method): To determine if a key is present in the HashSet, the method simply returns the Boolean value at the index equal to that key. If the value is True, the key is present; otherwise, it's absent.
```
def contains(self, key: int) -> bool:
    return self.data[key]
```

Each of the methods add, remove, and contains operate in O(1) time which is constant time complexity. This efficiency is achieved as the solution directly accesses the array index without any iteration or searching overhead, making these operations extremely fast for any size of data held in the HashSet.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example of operations being performed on the MyHashSet data structure:

Initialization: Upon creation of a MyHashSet object, an array data of size 1000001 is initialized with all values set to False.
- myHashSet = MyHashSet() initializes the MyHashSet with an empty set.
Adding Keys: Suppose we want to add the keys 3, 5, and 8 to the HashSet.
- myHashSet.add(3) sets data[3] to True.
- myHashSet.add(5) sets data[5] to True.
- myHashSet.add(8) sets data[8] to True.
- The array now has True at indices 3, 5, and 8, corresponding to the added keys.
Containing Key: We want to check if the keys 3 and 7 are in the HashSet.
- myHashSet.contains(3) returns True because data[3] is True, indicating that the key 3 is present in the HashSet.
- myHashSet.contains(7) returns False because data[7] is still False, indicating that the key 7 is not present in the HashSet.
Removing a Key: Now we decide to remove the key 5 from the HashSet.
- myHashSet.remove(5) sets data[5] back to False.
- If we now call myHashSet.contains(5), it will return False, indicating that the key 5 is no longer in the HashSet.

This example shows how each operation is executed with constant time complexity as it involves a single step of accessing or setting a value at a specific index in the array.

Solution Implementation

1class MyHashSet:
2    def __init__(self):
3        # Initialize an array with 1000001 elements, setting all to False.
4        # The index represents the key, and the value at that index
5        # represents the presence (True) or absence (False) of the key.
6        self.data = [False] * 1000001
7
8    def add(self, key: int) -> None:
9        # Add the key to the hash set by setting the value at the index 'key' to True.
10        self.data[key] = True
11
12    def remove(self, key: int) -> None:
13        # Remove the key from the hash set by setting the value at the index 'key' to False.
14        self.data[key] = False
15
16    def contains(self, key: int) -> bool:
17        # Check if the key is in the hash set by returning the value at the index 'key'.
18        return self.data[key]
19
20# Usage:
21# Create an instance of MyHashSet
22# my_hash_set = MyHashSet()
23# Add a key
24# my_hash_set.add(some_key)
25# Remove a key
26# my_hash_set.remove(some_key)
27# Check if a key exists
28# is_present = my_hash_set.contains(some_key)
29

1// Class representing a simple hash set data structure for integers
2class MyHashSet {
3    // Boolean array to store the presence of an integer in the set
4    // The array is sized to store the maximum value + 1 as an index
5    private boolean[] data;
6
7    // Constructor initializes the data array
8    public MyHashSet() {
9        data = new boolean[1000001]; // Set all values to 'false' by default
10    }
11
12    // Method to add an integer to the set
13    // Sets the array value at the index 'key' to 'true'
14    public void add(int key) {
15        data[key] = true;
16    }
17
18    // Method to remove an integer from the set
19    // Sets the array value at the index 'key' to 'false'
20    public void remove(int key) {
21        data[key] = false;
22    }
23
24    // Method to check if an integer is present in the set
25    // Returns 'true' if the value at the index 'key' is 'true', otherwise 'false'
26    public boolean contains(int key) {
27        return data[key];
28    }
29}
30
31/**
32 * Usage:
33 * MyHashSet hashSet = new MyHashSet();
34 * hashSet.add(key); // Adds the item 'key' to the hash set
35 * hashSet.remove(key); // Removes 'key' from the set if it's present
36 * boolean doesContain = hashSet.contains(key); // Returns 'true' if 'key' is present in the set, otherwise 'false'
37 */
38

1class MyHashSet {
2private:
3    // Using a fixed-size array to store the presence of keys
4    bool data[1000001];
5
6public:
7    // Constructor initializes the hash set
8    MyHashSet() {
9        // Set all values in the data array to false initially
10        memset(data, false, sizeof(data));
11    }
12
13    // Inserts a key into the hash set
14    void add(int key) {
15        data[key] = true;
16    }
17
18    // Removes a key from the hash set, if it exists
19    void remove(int key) {
20        data[key] = false;
21    }
22
23    // Checks if a key exists in the hash set
24    bool contains(int key) const {
25        return data[key];
26    }
27};
28
29// Usage example (not part of the class definition):
30// MyHashSet* myHashSet = new MyHashSet();
31// myHashSet->add(key);
32// myHashSet->remove(key);
33// bool doesContain = myHashSet->contains(key);
34

1// Define a global data storage for the HashSet. The `!` indicates that
2// the variable will be definitely assigned later.
3let hashSetData: boolean[];
4
5// Initialize the data storage for the HashSet with false values.
6// This is a setup function that needs to be called to create the storage.
7function initializeMyHashSet(): void {
8    // Allocate an array of boolean values with default value `false`
9    // The size is 10^6 + 1 to hold values within the range [0, 10^6]
10    hashSetData = new Array(10 ** 6 + 1).fill(false);
11}
12
13// Add a key to the HashSet by setting the value at the index `key` to true
14function addKeyToHashSet(key: number): void {
15    hashSetData[key] = true;
16}
17
18// Remove a key from the HashSet by setting the value at the index `key` to false
19function removeKeyFromHashSet(key: number): void {
20    hashSetData[key] = false;
21}
22
23// Check if a key exists in the HashSet by returning the value at the index `key`
24function containsKeyInHashSet(key: number): boolean {
25    return hashSetData[key];
26}
27
28// Example usage of the global HashSet implementation:
29// Initialize the HashSet before making any operations
30initializeMyHashSet();
31
32// Add a key to the hash set
33addKeyToHashSet(1);
34addKeyToHashSet(2);
35
36// Check if the hash set contains a key
37let containsKey1 = containsKeyInHashSet(1); // should return true
38let containsKey3 = containsKeyInHashSet(3); // should return false
39
40// Remove a key from the hash set
41removeKeyFromHashSet(2);
42

Time and Space Complexity

Time Complexity

add operation has a time complexity of O(1) because it accesses the array index directly and sets the value to True.
remove operation also has a time complexity of O(1) for the same reason, accessing the array index directly and setting the value to False.
contains operation has a time complexity of O(1) since it involves a single array lookup.

Each of the above operations perform in constant time irrespective of the number of elements in the hash set.

Space Complexity

The space complexity is O(N) where N = 1000001. This is because a fixed array of size 1000001 is allocated to store the elements of the hash set, independent of the actual number of elements stored at any time.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know