#705

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Design HashSet

Implement a custom HashSet without built-in libraries using array scanning and hash lookup for efficient membership checks.

array hash table linked list design hash function

Problem Statement

Design a HashSet without relying on any built-in hash table or set libraries. Implement the MyHashSet class with the following methods: add(key), remove(key), and contains(key) to store integer keys efficiently.

Your implementation should handle collisions, prevent duplicates, and support at most 10^4 method calls with keys in the range 0 to 10^6. Optimize operations using array scanning combined with hash lookup to meet time constraints.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2], [2]] Output [null, null, null, true, false, null, true, null, false]

Explanation MyHashSet myHashSet = new MyHashSet(); myHashSet.add(1); // set = [1] myHashSet.add(2); // set = [1, 2] myHashSet.contains(1); // return True myHashSet.contains(3); // return False, (not found) myHashSet.add(2); // set = [1, 2] myHashSet.contains(2); // return True myHashSet.remove(2); // set = [1] myHashSet.contains(2); // return False, (already removed)

Constraints

0 <= key <= 106
At most 104 calls will be made to add, remove, and contains.

Solution Approach

Choose a bucket structure

Initialize an array of buckets and map each key to a bucket index using a hash function. Use a linked list or dynamic array in each bucket to store actual keys, allowing O(1) average insertion and deletion while scanning the bucket linearly for collisions.

Implement add, remove, and contains

For add, first check if the key exists in the bucket to prevent duplicates, then append if absent. For remove, scan the bucket and delete the key if present. For contains, scan the bucket and return true if the key is found, otherwise return false.

Handle collisions efficiently

When multiple keys map to the same bucket, traverse the linked list or array linearly to check for duplicates and removals. Properly managing collisions ensures consistent performance and prevents overwriting or missing keys.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on bucket count and hash distribution: average O(1) for add, remove, and contains if collisions are minimal; worst-case O(n) if all keys hash to one bucket. Space complexity is proportional to the number of buckets plus the total stored keys.

What Interviewers Usually Probe

They may ask about handling collisions and why a linked list in each bucket works.
Expect questions on trade-offs between array scanning and hash table performance.
You might be prompted to explain worst-case scenarios when all keys hash to one bucket.

Common Pitfalls or Variants

Common pitfalls

Not handling duplicate keys correctly in add operations, causing redundant entries.
Ignoring collision handling, which can lead to incorrect contains or remove results.
Choosing too few buckets, increasing linear scanning time and degrading performance.

Follow-up variants

Implement a HashSet with open addressing instead of linked list buckets.
Support dynamic resizing of buckets when load factor exceeds a threshold.
Implement a HashMap variant that stores key-value pairs with similar hashing strategy.

FAQ

What is the best bucket size for Design HashSet to minimize collisions?

A bucket size proportional to the expected number of unique keys (around 10^4) ensures minimal collisions and near O(1) performance.

Can I use built-in set or hash table libraries in this problem?

No, the problem explicitly requires implementing a custom HashSet without any built-in hash table or set structures.

How does the array scanning plus hash lookup pattern work here?

Each key is hashed to a bucket index; scanning within the bucket checks for existence, enabling efficient add, remove, and contains operations.

What happens if multiple keys map to the same bucket?

Collisions are resolved by scanning the bucket’s linked list or array, ensuring each key is stored uniquely without overwriting others.

Is dynamic resizing necessary for this HashSet implementation?

It’s optional for this problem due to key constraints, but resizing can improve performance for larger key ranges or frequent insertions.

terminal

Solution

Solution 1: Static Array Implementation

Directly create an array of size $1000001$, initially with each element set to `false`, indicating that the element does not exist in the hash set.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class MyHashSet:
    def __init__(self):
        self.data = [False] * 1000001

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

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

    def contains(self, key: int) -> bool:
        return self.data[key]


# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)

Solution 2: Array of Linked Lists

We can also create an array of size $SIZE=1000$, where each position in the array is a linked list.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class MyHashSet:
    def __init__(self):
        self.data = [False] * 1000001

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

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

    def contains(self, key: int) -> bool:
        return self.data[key]


# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)

Continue Practicing

#706 design hashmap #745 prefix and suffix search #641 design circular deque