Insert Delete GetRandom O(1) - Duplicates allowed
Insert Delete GetRandom O(1) - Duplicates allowed is a hard design data structures problem solved with the hash map + array pattern.
The best approach, optimal (array + map of index sets), runs in O(1) average per operation time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (plain list, linear remove) up.
Problem
Design a class RandomizedCollection that stores a multiset of integers (the same value may be stored several times) and supports every operation in average O(1) time:
insert(val): add one copy ofval. Returntrueifvalwas not in the collection before this call, otherwisefalse(the copy is added either way).remove(val): if at least one copy ofvalis stored, remove one copy and returntrue; otherwise returnfalse.getRandom(): return a random stored value. The chance of each value is proportional to how many copies of it are stored: with{1, 1, 2}, the value1comes back with probability2/3.
Examples
Example 1
- Input
insert(3), insert(3), insert(8), getRandom(), remove(3), getRandom()- Output
true, false, true, 3 or 8, true, 3 or 8- Why
- The bag first holds {3, 3, 8}, so getRandom returns 3 with probability 2/3 and 8 with probability 1/3. After one 3 is removed the bag is {3, 8} and both are equally likely.
Example 2
- Input
insert(-5), remove(-5), remove(-5), insert(-5), insert(-5), getRandom()- Output
true, true, false, true, false, -5- Why
- The second remove fails because the bag is empty. Inserting -5 again succeeds as a new value, the next insert adds a duplicate and returns false, and only -5 can be drawn.
Constraints
-2^31 <= val <= 2^31 - 1getRandomis only called when the collection holds at least one value.- At most
2 * 10^5calls in total. - Each operation must run in average O(1) time.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (plain list, linear remove) | O(n) for insert and remove, O(1) for getRandom | O(n) |
| Optimal (array + map of index sets) | O(1) average per operation | O(n) |
1Brute force (plain list, linear remove)
O(n) for insert and remove, O(1) for getRandomThe contains check and the removal both scan the list, and removal shifts later elements.O(n)Every inserted copy is stored once.Keep every copy in a dynamic array. A random index gives the right probabilities automatically. Insert checks whether the value exists by scanning, and remove deletes the first copy it finds, shifting the elements after it.
- insert: fresh = list does not contain val; append val; return fresh.
- remove: find the first index of val; if none return false; delete it and return true.
- getRandom: return list[random index below the size].
class RandomizedCollection {
private final List<Integer> list = new ArrayList<>();
private final Random rnd = new Random();
public boolean insert(int val) {
boolean fresh = !list.contains(val);
list.add(val);
return fresh;
}
public boolean remove(int val) {
return list.remove(Integer.valueOf(val));
}
public int getRandom() {
return list.get(rnd.nextInt(list.size()));
}
}import random
class RandomizedCollection:
def __init__(self):
self.items = []
def insert(self, val: int) -> bool:
fresh = val not in self.items
self.items.append(val)
return fresh
def remove(self, val: int) -> bool:
if val not in self.items:
return False
self.items.remove(val)
return True
def getRandom(self) -> int:
return self.items[random.randrange(len(self.items))]class RandomizedCollection {
vector<int> items;
public:
bool insert(int val) {
bool fresh = find(items.begin(), items.end(), val) == items.end();
items.push_back(val);
return fresh;
}
bool remove(int val) {
auto it = find(items.begin(), items.end(), val);
if (it == items.end()) return false;
items.erase(it);
return true;
}
int getRandom() {
return items[rand() % items.size()];
}
};class RandomizedCollection {
constructor() {
this.items = [];
}
insert(val) {
const fresh = !this.items.includes(val);
this.items.push(val);
return fresh;
}
remove(val) {
const i = this.items.indexOf(val);
if (i === -1) return false;
this.items.splice(i, 1);
return true;
}
getRandom() {
return this.items[Math.floor(Math.random() * this.items.length)];
}
}2Optimal (array + map of index sets)
O(1) average per operationEach operation does a constant number of hash map, hash set and array end operations.O(n)The array and the index sets each hold one entry per stored copy.Keep all copies packed in an array so a random index is a fair draw weighted by count. Next to it keep a map from each value to the set of indices where it lives. Removal takes any index i of the value, copies the last element into slot i, moves that element's index from the last position to i in its own set, and pops the end. Nothing shifts, so every operation is O(1) on average.
- insert: add the new index (array size) to idx[val], append val, return true if idx[val] had been empty.
- remove: if idx[val] is missing or empty return false. Take any i from idx[val] and remove it.
- Let last = the final element. Put last at position i, add i to idx[last], remove the old last index from idx[last], pop the array. Delete idx[val] if it became empty.
- getRandom: return array[random index below the size].
class RandomizedCollection {
private final List<Integer> vals = new ArrayList<>();
private final Map<Integer, Set<Integer>> idx = new HashMap<>();
private final Random rnd = new Random();
public boolean insert(int val) {
Set<Integer> s = idx.computeIfAbsent(val, k -> new HashSet<>());
boolean fresh = s.isEmpty();
s.add(vals.size());
vals.add(val);
return fresh;
}
public boolean remove(int val) {
Set<Integer> s = idx.get(val);
if (s == null || s.isEmpty()) return false;
int i = s.iterator().next();
s.remove(i);
int lastPos = vals.size() - 1;
int last = vals.get(lastPos);
vals.set(i, last);
Set<Integer> ls = idx.get(last);
ls.add(i);
ls.remove(lastPos);
vals.remove(lastPos);
if (s.isEmpty()) idx.remove(val);
return true;
}
public int getRandom() {
return vals.get(rnd.nextInt(vals.size()));
}
}import random
class RandomizedCollection:
def __init__(self):
self.vals = []
self.idx = {}
def insert(self, val: int) -> bool:
s = self.idx.setdefault(val, set())
fresh = not s
s.add(len(self.vals))
self.vals.append(val)
return fresh
def remove(self, val: int) -> bool:
s = self.idx.get(val)
if not s:
return False
i = s.pop()
last_pos = len(self.vals) - 1
last = self.vals[last_pos]
self.vals[i] = last
ls = self.idx[last]
ls.add(i)
ls.discard(last_pos)
self.vals.pop()
if not s:
del self.idx[val]
return True
def getRandom(self) -> int:
return self.vals[random.randrange(len(self.vals))]class RandomizedCollection {
vector<int> vals;
unordered_map<int, unordered_set<int>> idx;
public:
bool insert(int val) {
auto& s = idx[val];
bool fresh = s.empty();
s.insert(vals.size());
vals.push_back(val);
return fresh;
}
bool remove(int val) {
auto it = idx.find(val);
if (it == idx.end() || it->second.empty()) return false;
int i = *it->second.begin();
it->second.erase(i);
int lastPos = vals.size() - 1;
int last = vals[lastPos];
vals[i] = last;
auto& ls = idx[last];
ls.insert(i);
ls.erase(lastPos);
vals.pop_back();
if (idx[val].empty()) idx.erase(val);
return true;
}
int getRandom() {
return vals[rand() % vals.size()];
}
};class RandomizedCollection {
constructor() {
this.vals = [];
this.idx = new Map();
}
insert(val) {
if (!this.idx.has(val)) this.idx.set(val, new Set());
const s = this.idx.get(val);
const fresh = s.size === 0;
s.add(this.vals.length);
this.vals.push(val);
return fresh;
}
remove(val) {
const s = this.idx.get(val);
if (!s || s.size === 0) return false;
const i = s.values().next().value;
s.delete(i);
const lastPos = this.vals.length - 1;
const last = this.vals[lastPos];
this.vals[i] = last;
const ls = this.idx.get(last);
ls.add(i);
ls.delete(lastPos);
this.vals.pop();
if (s.size === 0) this.idx.delete(val);
return true;
}
getRandom() {
return this.vals[Math.floor(Math.random() * this.vals.length)];
}
}Edge cases to test
- Inserting a value that is already present: it is still added, but the call returns false
- Removing one copy of a value that has several copies: the others stay and the call returns true
- Removing the copy that sits in the last slot of the array
- Removing a value that is not present returns false
- Many copies of one value and a single copy of another: getRandom must favour the frequent value
Hints
Hint 1
A plain list already gives the right probabilities: picking a uniform random index returns each value with probability equal to its share of the list. The hard part is removing quickly.
Hint 2
Store, for each value, the set of all indices where it appears in the list.
Hint 3
To delete in O(1), take any index of the value, move the last element of the list into that slot, fix the moved element's index set, and pop the end.
FAQ
What is the best time complexity for Insert Delete GetRandom O(1) - Duplicates allowed?
Optimal (array + map of index sets) runs in O(1) average per operation time and O(n) extra space. Each operation does a constant number of hash map, hash set and array end operations.
Which pattern does Insert Delete GetRandom O(1) - Duplicates allowed use?
It is a design data structures problem that uses the hash map + array pattern. Other problems with the same pattern: Insert Delete GetRandom O(1), Logger Rate Limiter, Design Parking System.
Is there a brute force solution for Insert Delete GetRandom O(1) - Duplicates allowed?
Yes. Brute force (plain list, linear remove) takes O(n) for insert and remove, O(1) for getRandom time and O(n) space. Keep every copy in a dynamic array.
Which edge cases should I test for Insert Delete GetRandom O(1) - Duplicates allowed?
Inserting a value that is already present: it is still added, but the call returns false; Removing one copy of a value that has several copies: the others stay and the call returns true; Removing the copy that sits in the last slot of the array; Removing a value that is not present returns false; Many copies of one value and a single copy of another: getRandom must favour the frequent value.