Insert Delete GetRandom O(1)

Medium

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]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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)];
}
}