Insert Delete GetRandom O(1) - Duplicates allowed
Problem
Design RandomizedCollection with insert(val), remove(val), and getRandom() in average O(1). Duplicates are allowed, and getRandom must produce each value with probability proportional to its multiplicity.
insert(1); insert(1); insert(2); getRandom(); remove(1)1 / 1 / 2 (mix) → array shrinksimport random
from collections import defaultdict
class RandomizedCollection:
def __init__(self):
self.arr = []
self.idx = defaultdict(set)
def insert(self, val):
self.idx[val].add(len(self.arr))
self.arr.append(val)
return len(self.idx[val]) == 1
def remove(self, val):
if not self.idx[val]:
return False
i = next(iter(self.idx[val]))
last = self.arr[-1]
self.arr[i] = last
self.idx[val].discard(i)
self.idx[last].discard(len(self.arr) - 1)
if i < len(self.arr) - 1:
self.idx[last].add(i)
self.arr.pop()
return True
def getRandom(self):
return random.choice(self.arr)class RandomizedCollection {
constructor() { this.arr = []; this.idx = new Map(); }
_set(v) { if (!this.idx.has(v)) this.idx.set(v, new Set()); return this.idx.get(v); }
insert(val) {
const s = this._set(val);
s.add(this.arr.length);
this.arr.push(val);
return s.size === 1;
}
remove(val) {
const s = this.idx.get(val);
if (!s || s.size === 0) return false;
const i = s.values().next().value;
const last = this.arr[this.arr.length - 1];
this.arr[i] = last;
s.delete(i);
this._set(last).delete(this.arr.length - 1);
if (i < this.arr.length - 1) this._set(last).add(i);
this.arr.pop();
return true;
}
getRandom() { return this.arr[Math.floor(Math.random() * this.arr.length)]; }
}class RandomizedCollection {
List<Integer> arr = new ArrayList<>();
Map<Integer, Set<Integer>> idx = new HashMap<>();
Random rng = new Random();
public boolean insert(int val) {
idx.computeIfAbsent(val, k -> new HashSet<>()).add(arr.size());
arr.add(val);
return idx.get(val).size() == 1;
}
public boolean remove(int val) {
Set<Integer> s = idx.get(val);
if (s == null || s.isEmpty()) return false;
int i = s.iterator().next();
int last = arr.get(arr.size() - 1);
arr.set(i, last);
s.remove(i);
idx.get(last).remove(arr.size() - 1);
if (i < arr.size() - 1) idx.get(last).add(i);
arr.remove(arr.size() - 1);
return true;
}
public int getRandom() { return arr.get(rng.nextInt(arr.size())); }
}class RandomizedCollection {
vector<int> arr;
unordered_map<int, unordered_set<int>> idx;
public:
bool insert(int val) {
idx[val].insert((int)arr.size());
arr.push_back(val);
return idx[val].size() == 1;
}
bool remove(int val) {
if (!idx.count(val) || idx[val].empty()) return false;
int i = *idx[val].begin();
int last = arr.back();
arr[i] = last;
idx[val].erase(i);
idx[last].erase((int)arr.size() - 1);
if (i < (int)arr.size() - 1) idx[last].insert(i);
arr.pop_back();
return true;
}
int getRandom() { return arr[rand() % arr.size()]; }
};Explanation
We need insert, remove, and a uniform getRandom all in average O(1), and this time duplicates are allowed. The backbone is a plain array arr holding all the values: getRandom just picks a random index, which is instant and naturally weights values by how many copies exist.
The challenge is fast removal. Removing from the middle of an array is normally slow, so we use the swap-with-last trick: copy the last element over the slot being removed, then pop the tail. To find a slot quickly we keep idx, a map from each value to a set of indices where that value lives (a set, not a single index, because duplicates need many positions).
On insert(val) we append to arr and add the new index into idx[val]. On remove(val) we grab any one index i from idx[val], overwrite arr[i] with the last value, and carefully fix the index bookkeeping: remove i from idx[val], remove the old tail index from the moved value's set, and (if the removed slot wasn't the tail) add i back for the moved value.
Example: insert 1, 1, 2, then remove(1). The array might be [1, 1, 2]; we take an index of value 1, copy the last value 2 into it, update 2's index set, and pop — leaving a valid [1, 2] with consistent maps.
Because each operation does a constant number of set and array actions, all three run in average constant time.