Log inSign up
easyLeetCodeNot Started

Design HashSet

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

Design a HashSet without using any built-in hash table libraries.

Implement MyHashSet class: - void add(key): Inserts the value key into the HashSet. - bool contains(key): Returns whether the value key exists in the HashSet or not. - void remove(key): Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.

Example 1 · Example 1: Basic Operations:

Input: add(1), add(2), contains(1), contains(3), add(2), contains(2), remove(2), contains(2)
Output: [null, null, true, false, null, true, null, false]
Explanation: - add(1), add(2)\n- contains(1) -> true\n- contains(3) -> false\n- add(2) (already exists, no change)\n- contains(2) -> true\n- remove(2)\n- contains(2) -> false.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the mechanics of hashing and collision chains.
  • Implement memory-efficient bitset and separate chaining structures.
  • Write complete, working implementations in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Design set data structure from scratch.
  • Fast lookup, insertion, and deletion.
  • Duplicate suppression.

Algorithmic Decision Tree:

  • Use prime modulus for uniform distribution.
  • Use linked list or dynamic array for collision chains.

Connected Patterns:

Design HashMapBloom FilterLRU Cache

1. Direct Boolean Array

Intuition

Create a boolean array of size 1000001. add sets arr[key] = true, remove sets arr[key] = false, and contains returns arr[key].

When to apply: When keys are bounded non-negative integers up to 106 and memory is plentiful.

Algorithm

  1. Step 1: Allocate boolean array of size 1000001 initialized to false.
  2. Step 2: add(key): arr[key] = true.
  3. Step 3: remove(key): arr[key] = false.
  4. Step 4: contains(key): return arr[key].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class MyHashSet {
7 vector<bool> table;
8public:
9 MyHashSet() : table(1000001, false) {}
10
11 void add(int key) {
12 table[key] = true;
13 }
14
15 void remove(int key) {
16 table[key] = false;
17 }
18
19 bool contains(int key) {
20 return table[key];
21 }
22};
23
24int main() {
25 MyHashSet mySet;
26 mySet.add(1);
27 mySet.add(2);
28 cout << boolalpha;
29 cout << "contains(1): " << mySet.contains(1) << endl; // true
30 cout << "contains(3): " << mySet.contains(3) << endl; // false
31 mySet.add(2);
32 cout << "contains(2): " << mySet.contains(2) << endl; // true
33 mySet.remove(2);
34 cout << "contains(2): " << mySet.contains(2) << endl; // false
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(1) strictly for all operations
  • Space complexity: O(M) where M = 10^6

2. Bitset Compression

Intuition

Map each key to integer index key / 32 and bit offset key % 32. Bitwise operations allow toggling and checking individual bits in O(1) time.

When to apply: When memory footprint must be reduced by 32x while maintaining strict O(1) performance.

Algorithm

  1. Step 1: Allocate integer array of size (1000001 / 32) + 1.
  2. Step 2: add(key): bits[key / 32] |= (1 << (key % 32)).
  3. Step 3: remove(key): bits[key / 32] &= ~(1 << (key % 32)).
  4. Step 4: contains(key): return (bits[key / 32] & (1 << (key % 32))) != 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class MyHashSet {
7 vector<int> bits;
8public:
9 MyHashSet() : bits(1000001 / 32 + 1, 0) {}
10
11 void add(int key) {
12 bits[key / 32] |= (1 << (key % 32));
13 }
14
15 void remove(int key) {
16 bits[key / 32] &= ~(1 << (key % 32));
17 }
18
19 bool contains(int key) {
20 return (bits[key / 32] & (1 << (key % 32))) != 0;
21 }
22};
23
24int main() {
25 MyHashSet mySet;
26 mySet.add(1);
27 mySet.add(2);
28 cout << boolalpha;
29 cout << "contains(1): " << mySet.contains(1) << endl;
30 cout << "contains(3): " << mySet.contains(3) << endl;
31 mySet.add(2);
32 cout << "contains(2): " << mySet.contains(2) << endl;
33 mySet.remove(2);
34 cout << "contains(2): " << mySet.contains(2) << endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(1) for all operations
  • Space complexity: O(M / 32) integers

3. Separate Chaining with Prime Modulo Buckets

Intuition

Distribute elements into 769 buckets using hash function key % 769. Duplicate checks are performed locally within the target bucket. Average lookup time is O(1).

When to apply: Standard production architecture for hash sets.

Algorithm

  1. Step 1: Initialize array of 769 buckets.
  2. Step 2: add(key): if contains(key) is false, append key to bucket[key % 769].
  3. Step 3: contains(key): scan bucket[key % 769]; return true if found, else false.
  4. Step 4: remove(key): scan bucket[key % 769]; erase key if found.

Interactive Trace for MyHashSet

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: add(1)
Visual state
Values and pointers at this exact step
pointers
S
empty
[1]
0
1
↑ hash
Check / comparison
1 % 769 = 1
Decision / next transition
Bucket 1: [1].
Why this step matters

Step 1: add(1). 1 % 769 = 1. Bucket 1 holds key 1.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <list>
4#include <algorithm>
5
6using namespace std;
7
8class MyHashSet {
9 static const int BUCKETS = 769;
10 vector<list<int>> table;
11
12 int hash(int key) {
13 return key % BUCKETS;
14 }
15
16public:
17 MyHashSet() : table(BUCKETS) {}
18
19 void add(int key) {
20 int idx = hash(key);
21 for (int k : table[idx]) {
22 if (k == key) return;
23 }
24 table[idx].push_back(key);
25 }
26
27 void remove(int key) {
28 int idx = hash(key);
29 table[idx].remove(key);
30 }
31
32 bool contains(int key) {
33 int idx = hash(key);
34 for (int k : table[idx]) {
35 if (k == key) return true;
36 }
37 return false;
38 }
39};
40
41int main() {
42 MyHashSet mySet;
43 mySet.add(1);
44 mySet.add(2);
45 cout << boolalpha;
46 cout << "contains(1): " << mySet.contains(1) << endl; // true
47 cout << "contains(3): " << mySet.contains(3) << endl; // false
48 mySet.add(2);
49 cout << "contains(2): " << mySet.contains(2) << endl; // true
50 mySet.remove(2);
51 cout << "contains(2): " << mySet.contains(2) << endl; // false
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(1) average time
  • Space complexity: O(B + N) where B = 769

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Direct Boolean ArrayO(1) strictly for all operationsO(M) where M = 10^6Allocate a boolean array of size 1,000,001. Set arr[key] = true/false.Static memory footprint.
2.Better — Bitset / Bit Manipulation ArrayO(1) strictly for all operationsO(M / 64) 64-bit integersCompress the boolean array using bit manipulation: word index = key / 64, bit offset = key % 64.Bitwise masking.
3.Optimal — Separate Chaining with Prime Modulo BucketsOptimalO(1) average timeO(B + N) where B = 769Allocate 769 buckets. Each bucket is a list of keys. Hash key via key % 769.Bucket chain search.

Common Pitfalls & Crucial Edge Cases

Using a giant boolean array `bool[1000001]` without explanation

Always explain hash buckets and collision resolution first, then mention bitset as a memory-optimized alternative.

Appending duplicate keys on multiple `add` calls

Must check if key is already present in the bucket before adding.

Inefficient bucket deletion

In array-based buckets, swapping with the last element enables O(1) removal.

Crucial Edge Cases to Validate:

  • Adding an already existing key — Set must remain unchanged without duplicates.
  • Removing a key not in the set — Operation succeeds silently without error.
  • key = 0 and key = 10^6 — Lowest and highest valid integer keys.
  • Multiple keys hashing to the same bucket — Verified that separate chaining traverses the bucket list correctly.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Demonstrate separate chaining with a prime number modulus (e.g. 769).
  2. Mention the bitset optimization: show that a bitset uses 8x less memory than a boolean array (1 bit vs 1 byte).
  3. Discuss amortized complexity and collision resolution trade-offs.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the fundamental difference between a HashSet and a HashMap in data structure design?

2.How can a bitset (bit array) implement an ultra-compact HashSet for integer keys up to 106?

3.What is the time complexity of add, remove, and contains in a well-distributed hash set?

Back to DSA Sheet