Insert Delete GetRandom O(1)
Description
Keep a set of integers that can add a value, remove one, and hand out one of its values at random.
Implement the RandomizedSet class:
RandomizedSet()starts an empty set.bool insert(int val)addsvalif it isn't in the set. It returns true if it added it, and false ifvalwas already there.bool remove(int val)takesvalout if it's in the set. It returns true if it removed it, and false ifvalwasn't there.int getRandom()returns one of the set's values at random, each value with the same chance. The set holds at least one value whenever it's called.
Each call must take O(1) time on average.
getRandom's answer is random, so the tests check it instead of comparing it: each answer shows as true when it's one of the set's values, and over a long run of answers on the same set, every value has to come up about as often as the others.
Examples
Example 1
Input:
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output: [null, true, false, true, true, true, false, true]
Explanation: insert(1) adds 1; remove(2) fails, since 2 isn't there; insert(2) adds it. getRandom may answer 1 or 2, and an answer in the set shows as true. remove(1) takes 1 out, insert(2) fails because 2 is already in, and the last getRandom can only answer 2.
Example 2
Input:
["RandomizedSet", "remove", "insert", "insert", "insert", "getRandom", "getRandom", "remove", "getRandom"]
[[], [0], [-2147483648], [2147483647], [-2147483648], [], [], [2147483647], []]
Output: [null, false, true, true, false, true, true, true, true]
Explanation: Removing from an empty set fails. The two ends of the range go in, and the second insert of −2,147,483,648 fails. With 2,147,483,647 removed, getRandom has one value left to answer.
Example 3
Input:
["RandomizedSet", "insert", "remove", "remove", "insert", "getRandom"]
[[], [7], [7], [7], [7], []]
Output: [null, true, true, false, true, true]
Explanation: A value can leave and come back: 7 is removed once, the second remove fails, and 7 goes in again.
Constraints
- −2³¹ ≤ val ≤ 2³¹ − 1
- At most 2 × 10⁵ calls are made to insert, remove and getRandom
- The set holds at least one value whenever getRandom is called
Editorial
Brute Force
Intuition
A hash set already inserts and removes in O(1) on average. What it can't do is hand out its k-th value, which a random pick needs. So for each getRandom, copy the set into a list and pick a random index of the copy.
Step-by-Step Explanation
Let's trace Example 1:
insert(1): 1 isn't in the set, so it goes in and the call returns true.remove(2): 2 isn't in the set, so the call returns false and nothing changes.insert(2): 2 isn't in the set, so it goes in and the call returns true.getRandom(): the set can't hand out its k-th value, so this copies its 2 values into a list and picks one at random.remove(1): 1 comes out of the set, and the call returns true.insert(2): 2 is already in the set, so the call returns false.getRandom(): the set can't hand out its k-th value, so this copies its 1 value into a list and picks one at random, which can only be 2.
A Set, Copied for Each Pick — Inserts and removes go straight to the set; every getRandom copies all of it first.
Algorithm
- Keep the values in a hash set.
- insert and remove add and delete
val, returning whether the set changed. - getRandom copies the set into a list and returns the value at a random index of the copy.
Code
class RandomizedSet {
unordered_set<int> values;
mt19937 rng{random_device{}()};
public:
RandomizedSet() {
}
bool insert(int val) {
return values.insert(val).second;
}
bool remove(int val) {
return values.erase(val) > 0;
}
int getRandom() {
vector<int> copy(values.begin(), values.end()); // a set can't hand out its k-th value: copy it first
return copy[uniform_int_distribution<int>(0, (int) copy.size() - 1)(rng)];
}
};
import random
class RandomizedSet:
def __init__(self):
self.values = set()
def insert(self, val: int) -> bool:
if val in self.values:
return False
self.values.add(val)
return True
def remove(self, val: int) -> bool:
if val not in self.values:
return False
self.values.remove(val)
return True
def getRandom(self) -> int:
return random.choice(list(self.values)) # a set can't hand out its k-th value: copy it first
class RandomizedSet {
private final Set<Integer> values = new HashSet<>();
private final Random rng = new Random();
public RandomizedSet() {
}
public boolean insert(int val) {
return values.add(val);
}
public boolean remove(int val) {
return values.remove(val);
}
public int getRandom() {
List<Integer> copy = new ArrayList<>(values); // a set can't hand out its k-th value: copy it first
return copy.get(rng.nextInt(copy.size()));
}
}
var RandomizedSet = function() {
this.values = new Set();
};
RandomizedSet.prototype.insert = function(val) {
if (this.values.has(val)) return false;
this.values.add(val);
return true;
};
RandomizedSet.prototype.remove = function(val) {
return this.values.delete(val);
};
RandomizedSet.prototype.getRandom = function() {
const copy = [...this.values]; // a set can't hand out its k-th value: copy it first
return copy[Math.floor(Math.random() * copy.length)];
};
Complexity Analysis
Time Complexity: O(1) for insert and remove, O(n) for getRandom
insert and remove are one hash set operation on average; getRandom copies all n values.
Space Complexity: O(n)
The set, and a copy of it during each getRandom.
Why This Approach Is Not Efficient
Every pick copies the whole set. On a test of 10⁴ values and then 10⁴ picks, the copies took 1.03 s in Python on the judge, the list and map below 68 ms, and on the largest tests, 10⁵ picks from 10⁵ values, it ran out of time in every language. The copy builds the same list over and over. Keep that list all along instead, and a pick is one random index.
Optimal Approach - A List and a Map of Indexes
Intuition
A list picks at random in O(1): any index from 0 to its length − 1. What a list can't do fast is find a value, to check an insert or to remove it. A hash map from each value to its index in the list finds it at once. The one hard part is removing: taking a value out of the middle of a list shifts everything after it. Instead, move the last value into the gap, tell the map its new index, and drop the last slot. The list's order never mattered, only which values it holds.
Step-by-Step Explanation
Let's trace Example 1 again:
insert(1): 1 goes on the end of the list, at index 0, andwhererecords it.remove(2): 2 isn't inwhere, so the call returns false and nothing changes.insert(2): 2 goes on the end of the list, at index 1, andwhererecords it.getRandom(): a random index from 0 to 1, each as likely, and the answer is the value there.remove(1): 1 is at index 0. The last value, 2, moves into index 0,whererecords its new index, and the list's last slot goes.insert(2): 2 is inwherealready, so the call returns false.getRandom(): one value, so the random index can only be 0, and the answer is 2.
A List and a Map of Indexes — Inserts go on the end; a remove moves the last value into the gap; a pick is one random index.
Algorithm
- Keep a list
valuesand a mapwherefrom each value to its index in the list. - insert: if
valis inwhere, return false. Otherwise record its index,len(values), and append it. - remove: if
valisn't inwhere, return false. Otherwise take its indexiout ofwhereand pop the last value. Ifiwas not the last index, put the popped value atiand recordifor it inwhere. - getRandom: return the value at a random index from 0 to
len(values) − 1.
Code
class RandomizedSet {
vector<int> values; // the values, in no order
unordered_map<int, int> where; // value -> its index in values
mt19937 rng{random_device{}()};
public:
RandomizedSet() {
}
bool insert(int val) {
if (where.count(val)) return false;
where[val] = values.size();
values.push_back(val);
return true;
}
bool remove(int val) {
auto it = where.find(val);
if (it == where.end()) return false;
int i = it->second, last = values.back();
values.pop_back();
where.erase(it);
if (i < (int) values.size()) { // val wasn't the last value: the last one takes its place
values[i] = last;
where[last] = i;
}
return true;
}
int getRandom() {
return values[uniform_int_distribution<int>(0, (int) values.size() - 1)(rng)];
}
};
import random
class RandomizedSet:
def __init__(self):
self.values = [] # the values, in no order
self.where = {} # value -> its index in values
def insert(self, val: int) -> bool:
if val in self.where:
return False
self.where[val] = len(self.values)
self.values.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.where:
return False
i, last = self.where.pop(val), self.values.pop()
if i < len(self.values): # val wasn't the last value: the last one takes its place
self.values[i] = last
self.where[last] = i
return True
def getRandom(self) -> int:
return random.choice(self.values)
class RandomizedSet {
private final List<Integer> values = new ArrayList<>(); // the values, in no order
private final Map<Integer, Integer> where = new HashMap<>(); // value -> its index in values
private final Random rng = new Random();
public RandomizedSet() {
}
public boolean insert(int val) {
if (where.containsKey(val)) return false;
where.put(val, values.size());
values.add(val);
return true;
}
public boolean remove(int val) {
Integer i = where.remove(val);
if (i == null) return false;
int last = values.remove(values.size() - 1);
if (i < values.size()) { // val wasn't the last value: the last one takes its place
values.set(i, last);
where.put(last, i);
}
return true;
}
public int getRandom() {
return values.get(rng.nextInt(values.size()));
}
}
var RandomizedSet = function() {
this.values = []; // the values, in no order
this.where = new Map(); // value -> its index in values
};
RandomizedSet.prototype.insert = function(val) {
if (this.where.has(val)) return false;
this.where.set(val, this.values.length);
this.values.push(val);
return true;
};
RandomizedSet.prototype.remove = function(val) {
if (!this.where.has(val)) return false;
const i = this.where.get(val), last = this.values.pop();
this.where.delete(val);
if (i < this.values.length) { // val wasn't the last value: the last one takes its place
this.values[i] = last;
this.where.set(last, i);
}
return true;
};
RandomizedSet.prototype.getRandom = function() {
return this.values[Math.floor(Math.random() * this.values.length)];
};
Complexity Analysis
Time Complexity: O(1) per call
Each call is a hash map lookup or two and work at the list's end, on average.
Space Complexity: O(n)
The list and the map, one entry each per value.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Forgetting where the moved value went. self.values[i] = last
On the calls below it returns [null, true, true, true, true, true, false]; the answer is [null, true, true, true, true, true, true].
["RandomizedSet", "insert", "insert", "insert", "remove", "remove", "getRandom"]
[[], [1], [2], [3], [1], [3], []]
Removing from the middle moves the last value into the gap, so the map has to learn its new index. Left at its old index, past the end of the list, the next remove of that value pops whatever is last instead, and getRandom can answer with a value that was removed.
randint's top end. return self.values[random.randint(0, len(self.values))]
On the calls below it fails with IndexError (list index out of range) instead of returning [null, true, true, true, true, true, true, true, true, true, true, true].
["RandomizedSet", "insert", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[], [4], [], [], [], [], [], [], [], [], [], []]
random.randint(a, b) includes b, so randint(0, len(values)) can answer len(values), one past the last index, and the list access fails. random.choice, or randrange(len(values)), stays inside.
Where This Pattern Is Taught
This problem practises putting two structures together so each covers what the other can't: a list to pick from by index, a map to find each value's index. It's taught in Designing a Data Structure.