Back to solutions

Design HashSet

EasyArrays

Implement a set of integers supporting add, remove, contains.

Open problem
Constraints
  • 0 <= key <= 10^6
  • 1 <= q <= 10^4

Direct-address boolean array

Time O(1) per operationSpace O(max key)

Because keys are bounded by 10^6, allocate a boolean array of that size. The key itself is the index: add sets the slot true, remove sets it false, and contains reads it. Every operation is O(1).

Key terms
direct addressing:
Using the key as a direct array index when the key range is small enough to allocate.
load factor:
Ratio of stored items to table slots; direct addressing avoids collisions entirely.
class MyHashSet {
    vector<bool> data;
public:
    MyHashSet() : data(1000001, false) {}
    void add(int key) { data[key] = true; }
    void remove(int key) { data[key] = false; }
    bool contains(int key) { return data[key]; }
};
Step by step
  1. Create a boolean array sized to the max possible key plus one, all false.
  2. add(key): set array[key] = true.
  3. remove(key): set array[key] = false.
  4. contains(key): return array[key].