Insert Delete GetRandom O(1)
Medium · Design · Array · Hash Table · Math · Design · Randomized
Problem
Build a set of integers with three operations, each running in average O(1) time:
- insert(val) adds val if it is not already there. Return True if it was added and False if it was already present.
- remove(val) deletes val if it is there. Return True if it was removed and False if it was not present.
- getRandom() returns one of the current members uniformly at random: with k members, each comes back with probability 1/k. It is only called when the set is not empty.
The hard part is getting all three at once. A hash set adds and removes in O(1) but cannot pick a random member without walking through it. A list picks a random position in O(1) but removes from the middle in O(n).
Tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments, and calls returning nothing report None. Because getRandom is random, the expected list shows one possible run. Any member of the set at that moment is accepted. The long tests also count the draws: when getRandom is called thousands of times on a set that does not change, each member's count must be within 7 standard deviations of its fair share. A fair getRandom falls outside that band with probability below one in a billion. An implementation that favours one member, or never returns another, fails.
Examples
Input: insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom() Output: True, False, True, 1 or 2, True, False, then 2
remove(2) fails because 2 is not in the set yet. The first getRandom may return either member, each half the time. After 1 is removed only 2 is left, and inserting 2 again changes nothing.
Input: insert(5), insert(5), getRandom(), remove(5), insert(5) Output: True, False, 5, True, then True
A value is stored once, so the second insert(5) is refused. After removing it, it can be inserted again.
Constraints
- -2^31 <= val <= 2^31 - 1
- Up to 2 * 10^5 calls in total
- getRandom is only called when the set has at least one member
- Each operation must run in average O(1) time
Approaches
- A plain set, copied on every draw — time O(1) insert/remove, O(n) getRandom, space O(n)
Follow-up
What if the same value may be inserted several times and every copy counts (LeetCode 381)? Keep a set of indices per value instead of a single index.
Related problems
Start free on Cariara · Coding problems · System design studio
