Insert Delete GetRandom O(1)
Build a collection of numbers that supports three things, each in constant time : insert(value) adds a value and says whether it was new, remove(value) takes a value out and says whether it was there, and getRandom() returns one of the stored values with every value equally likely. A hash map alone gives fast insert and remove but cannot pick a random value. An array alone gives a fast random pick but slow removal. The answer is to keep both at once : an array holding the values, and a hash map from each value to the position it sits at in that array. Removal is the clever part. Never shift the array. Instead move the last value into the hole , correct its position in the map, then shorten the array by one. That keeps the array packed with no gaps, which is what makes a random pick fair and instant. The entry function takes two arrays so the result can be checked: operations is a list of names such as "insert", and values holds the arguments for each one. Because getRandom really is random, this exercise reports true for a getRandom call when the value it handed back was genuinely in the collection, rather than the value itself. That keeps the test answers the same on every run.
Constraints
- -231 ≤ value ≤ 231 - 1
- At most 2 × 105 calls are made in total
- getRandom is only called when at least one value is stored
- Every stored value must be equally likely to be returned by getRandom
Example
operations = ["insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"], values = [[1], [2], [2], [], [1], [2], []][true, false, true, true, true, false, true]Explanation insert(1) is new so it answers true. remove(2) answers false because 2 was not there. insert(2) is new. getRandom returns 1 or 2, both of which are stored, so it is reported as true. remove(1) answers true. insert(2) answers false because 2 is already stored. The last getRandom can only return 2.
In plain terms
- Constant time
- The work does not grow as the collection grows. Adding the ten thousandth value costs the same as adding the first.
- Index map
- The hash map used here. Its key is a stored value and its value is the position of that value in the array, so a value can be found without searching.
- Swap with the last
- The removal trick: copy the final item of the array over the item being removed, then drop the final slot. It leaves no gap and touches only two positions.
- Packed array
- An array with no empty slots in the middle. It is what lets a random position between 0 and the size be picked and always land on a real value.
One cell per key of the index map, value = the position in the array, plus the size
The collection starts with an empty array and an empty index map.
What happens in this step
items = [] and positions = empty The first three cells will show map entries once values arrive. The last cell tracks the size, which is 0 right now.
Steps to visualize
- The first three cells are entries of the index map: the label is a stored value and the cell value is where it sits in the array.
- The last cell is the size, which is how many values the array currently holds.
- insert puts the value at the end of the array and writes that position into the map.
- remove moves the last value into the freed position, fixes that value in the map, and shrinks the size by one.
- getRandom picks a position between 0 and size minus 1, so a packed array means a fair pick.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
The collection starts with an empty array and an empty index map.
What happens in this step
items = [] and positions = empty The first three cells will show map entries once values arrive. The last cell tracks the size, which is 0 right now.
Solution
function randomizedSet(operations, values) {
function RandomizedSet() {
this.items = [];
this.positions = new Map();
}
RandomizedSet.prototype.insert = function (value) {
if (this.positions.has(value)) {
return false;
}
this.positions.set(value, this.items.length);
this.items.push(value);
return true;
};
RandomizedSet.prototype.remove = function (value) {
if (!this.positions.has(value)) {
return false;
}
const index = this.positions.get(value);
const last = this.items[this.items.length - 1];
this.items[index] = last;
this.positions.set(last, index);
this.items.pop();
this.positions.delete(value);
return true;
};
RandomizedSet.prototype.getRandom = function () {
const pick = Math.floor(Math.random() * this.items.length);
return this.items[pick];
};
const set = new RandomizedSet();
const results = [];
for (let i = 0; i < operations.length; i++) {
const name = operations[i];
const args = values[i];
if (name === 'insert') {
results.push(set.insert(args[0]));
} else if (name === 'remove') {
results.push(set.remove(args[0]));
} else {
results.push(set.positions.has(set.getRandom()));
}
}
return results;
}- Time
- O(1) for every call
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
operations = ["insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"], values = [[1], [2], [2], [], [1], [2], []] | [true, false, true, true, true, false, true] | example from the description |
operations = ["insert", "insert"], values = [[5], [5]] | [true, false] | inserting a value that is already stored |
operations = ["remove", "insert", "remove", "remove"], values = [[9], [9], [9], [9]] | [false, true, true, false] | removing from an empty collection, then removing the same value twice |
operations = [], values = [] | [] | nothing is called at all |
operations = ["insert", "insert", "remove", "insert", "getRandom"], values = [[1], [2], [2], [3], []] | [true, true, true, true, true] | removing the value that already sits at the end, where the swap is with itself |
five values inserted, two removed, then two random picks | [true, true, true, true, true, true, true, true, true] | a longer run where random picks still only land on stored values |