705. Design HashSet

EasyDesignArrayHash TableLinked ListHash Function
Leetcode Link

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:

  1. 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.

  2. Add: To add a key, we simply set the value at the index corresponding to the key in the array to True.

  3. Remove: To remove a key, we set the value at the index corresponding to the key in the array back to False.

  4. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which data structure is used in a depth first search?

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:

  1. 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.

    1def __init__(self):
2    self.data = [False] * 1000001

  2. 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.

    1def add(self, key: int) -> None:
2    self.data[key] = True

  3. 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.

    1def remove(self, key: int) -> None:
2    self.data[key] = False

  4. 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.

    1def contains(self, key: int) -> bool:
2    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.

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

How does quick sort divide the problem into subproblems?

Example Walkthrough

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

  1. 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.

  2. 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.

  3. 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.

  4. 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
Not Sure What to Study? Take the 2-min Quiz：

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of these pictures shows the visit order of a depth-first search?

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫