Design HashSet

Design HashSet: the approach in brief

The problem

Implement a class named MyHashSet that stores a collection of integer keys. A key can appear at most once, and the set initially contains no keys. Built-in hash set or hash table libraries must not be used.

Pattern

Design HashSet is a Array/Matrix Manipulation Patterns problem, in the Hashing - Previously Seen / Existence Check subpattern. The pattern covers in-place operations, hashing, prefix sums, spiral traversal, and cyclic sort

Approach outline

1. Keep the set's membership state inside the `MyHashSet` object so it persists across method calls.
2. The allowed key range is bounded, so consider representing membership by position rather than storing the keys in a library collection.
3. Use a boolean entry for each possible integer key; the key itself can identify that entry directly.

Complexity

The reference solution runs in O(1) per add, remove, or contains operation time and O(10^6) space.