Insert Delete GetRandom O(1)
Problem
Design a set with insert(val), remove(val) (each returns whether it changed the set) and getRandom() (returns each current element with equal probability). Every operation must be O(1) on average.
Example 1
Input: insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom() Output: true, false, true, 1 or 2, true, false, 2
Test cases
Case 1
Input: new RandomizedSet() .insert(1) .remove(2) .insert(2) .remove(1) .insert(2) .getRandom() Expected: [true,false,true,true,false,2]
Case 2
Input: new RandomizedSet() .insert(3) .getRandom() .remove(3) .insert(4) .getRandom() Expected: [true,3,true,true,4]
Case 3
Input: new RandomizedSet() .insert(5) .insert(5) .remove(5) .remove(5) Expected: [true,false,true,false]
View solutionHide solution1 approach
1. Array + value→index map
Time O(1) average for every operationSpace O(n)
The array gives O(1) random access. To delete in O(1), move the last element into the removed slot and update its index.
class RandomizedSet { constructor() { this.arr = []; this.idx = new Map(); } insert(v) { if (this.idx.has(v)) return false; this.idx.set(v, this.arr.length); this.arr.push(v); return true; } remove(v) { if (!this.idx.has(v)) return false; const i = this.idx.get(v), last = this.arr[this.arr.length - 1]; this.arr[i] = last; this.idx.set(last, i); this.arr.pop(); this.idx.delete(v); return true; } getRandom() { return this.arr[Math.floor(Math.random() * this.arr.length)]; }}