Domain 1EasyCORE

Design HashSet

The problem requires designing a `HashSet` data structure without using any built-in hash table libraries. The `MyHashSet` class should support three operations: `add`, `remove`, and `contains`. The `add` method inserts a key into the set, `remove` deletes a key from the set if it exists, and `contains` checks if a key is present in the set.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Hash Table#Design

705. Design HashSet

Model: qwen2.5-coder:14b
Topics: Hash Table,Design
FAANG asked: 1
Acceptance rate: 64.5%


Problem Breakdown

The problem requires designing a HashSet data structure without using any built-in hash table libraries. The MyHashSet class should support three operations: add, remove, and contains. The add method inserts a key into the set, remove deletes a key from the set if it exists, and contains checks if a key is present in the set.

Inputs:

  • Methods: add(key), remove(key), contains(key)
  • Constraints: 0 <= key <= 10^6
  • Maximum operations: At most 10^4 calls

Outputs:

  • add: No return value
  • remove: No return value
  • contains: Boolean indicating presence of the key

Implicit Constraints/Edge Cases:

  • Duplicates: Adding a key that already exists should not change the set.
  • Non-existent keys: Removing or checking for non-existent keys should handle gracefully without errors.

Intuition

A brute-force approach would involve using a list to store all elements and perform linear searches for add, remove, and contains operations. This approach is inefficient with time complexity of O(n) for each operation due to the need to scan through the entire list.

The key insight is to use an array-based hash set to achieve average constant time complexity for these operations. By using an array where each index represents a potential key value, we can quickly determine if a key exists and perform insertions or deletions efficiently.

Approach

  1. Data Structure Choice: Use an array of size 10^6 + 1 (to cover the range of keys from 0 to 10^6) where each index corresponds to a potential key value.
  2. Initialization: Initialize all elements in the array to False, indicating that no keys are present initially.
  3. Add Operation:
    • Set the boolean value at the index corresponding to the key to True.
  4. Remove Operation:
    • Set the boolean value at the index corresponding to the key to False.
  5. Contains Operation:
    • Return the boolean value at the index corresponding to the key.

This approach leverages direct indexing, which provides average constant time complexity for all operations.

Complexity Analysis

  • Time Complexity: O(1) for each of add, remove, and contains operations.
    • Direct array access is constant time.
  • Space Complexity: O(n), where n is the range of possible keys (10^6 + 1 in this case).
    • Fixed-size array to store boolean values.

Solution

class MyHashSet:
    def __init__(self):
        # Initialize an array of size 10^6 + 1 with all values set to False
        self.size = 10**6 + 1
        self.set = [False] * self.size

    def add(self, key: int) -> None:
        # Set the value at index 'key' to True
        self.set[key] = True

    def remove(self, key: int) -> None:
        # Set the value at index 'key' to False
        self.set[key] = False

    def contains(self, key: int) -> bool:
        # Return the value at index 'key'
        return self.set[key]

Edge Cases Handled

  • Adding a duplicate key: The add method will not change the set since setting an already True index to True has no effect.
  • Removing a non-existent key: The remove method will not cause errors or alter the set since setting a False index to False is harmless.
  • Checking for non-existent keys: The contains method will correctly return False for keys that have never been added.