Back to solutions

Insert Delete Get Random O(1)

MediumArrays

A set supporting insert, remove, and uniform random in O(1).

Open problem
Constraints
  • -2^31 <= val <= 2^31 - 1
  • getRandom is only called when non-empty

Array plus index map

Time O(1) average per operationSpace O(n)

Store the elements in a dynamic array for O(1) random access and a hash map from value to its array index. Insert appends and records the index. Remove swaps the target with the last element, updates that element's index, then pops the tail, so deletion stays O(1) without leaving holes.

Key terms
swap-with-last:
Deleting from the middle of an array in O(1) by moving the last element into the gap.
index map:
A hash map recording where each value lives in the array.
bool insert(int val) {
    if (idx.count(val)) return false;
    idx[val] = arr.size(); arr.push_back(val); return true;
}
bool remove(int val) {
    auto it = idx.find(val);
    if (it == idx.end()) return false;
    int i = it->second, last = arr.back();
    arr[i] = last; idx[last] = i; arr.pop_back(); idx.erase(it);
    return true;
}
Step by step
  1. insert: if present return false; else append and record its index in the map.
  2. remove: if absent return false; copy the last element over the target slot, fix its index, pop the tail, erase the value.
  3. getRandom: pick a uniform random array index (the harness uses the last index for determinism).
  4. All operations touch only a constant number of array/map entries.