468/670

468. Design HashSet

Easy

Build an integer set from scratch — pretend your language's built-in set and map types don't exist.

Implement a class MyHashSet with three operations:

add(key) — put key into the set. Adding a key that is already present changes nothing.
remove(key) — take key out of the set. Removing a key that isn't there changes nothing.
contains(key) — return true if key is currently in the set, false otherwise.

Every key is an integer between 0 and 10^6. Your class receives a stream of these calls and only contains produces output. The interesting part is making all three operations fast without leaning on a library hash table.

Example 1:

Input: MyHashSet(); add(1), add(2), contains(1), contains(3), add(2), contains(2)

Output: [true, false, true]

Explanation: 1 and 2 are added, so contains(1) is true. 3 was never added, so contains(3) is false. Adding 2 a second time is a no-op; contains(2) is still true.

Example 2:

Input: MyHashSet(); add(5), contains(5), remove(5), contains(5), remove(5), contains(5)

Output: [true, false, false]

Explanation: After add(5) the set contains 5. remove(5) deletes it, so the next contains(5) is false. The second remove(5) targets a missing key and does nothing.

Constraints:

0 ≤ key ≤ 10⁶
At most 10⁴ calls total to add, remove, and contains
Do not use built-in hash set / hash map / dictionary types

Hints:

Correctness first: a plain list plus a linear scan implements all three operations. What does each call cost as the set grows?

The keys live in a small, known range — 0 to 10^6. An array of booleans indexed by the key itself answers contains in one step.

A real hash set shrinks that giant array: pick a fixed number of buckets B, send each key to bucket key % B, and keep a short list (chain) per bucket. If keys spread evenly, every chain stays tiny.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: add(1), add(2), contains(1), contains(3), add(2), contains(2)

Expected output: [true, false, true]