Insert Delete GetRandom O(1)
Insert Delete GetRandom O(1) is a medium design data structures problem solved with the hash map + array pattern.
The best approach, optimal (array + value-to-index map), runs in O(1) average for every operation time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (hash set, walk to a random position) up.
Problem
Build a RandomizedSet class that stores distinct integers and supports three operations, each in average O(1) time:
insert(val): addvalif it is not already stored. Returntrueif it was added,falseif it was already there.remove(val): deletevalif it is stored. Returntrueif it was removed,falseif it was not there.getRandom(): return one of the stored values, chosen uniformly at random, so every stored value has the same chance of being returned.
Examples
Example 1
- Input
insert(4), insert(4), insert(9), remove(4), getRandom(), remove(7)- Output
true, false, true, true, 9, false- Why
- The second insert of 4 fails because 4 is already there. After removing 4 only 9 is left, so getRandom must return 9. 7 was never added, so removing it fails.
Example 2
- Input
insert(-2), insert(6), getRandom(), remove(-2), insert(-2), getRandom()- Output
true, true, -2 or 6, true, true, -2 or 6- Why
- With two values stored, getRandom returns either one, each with probability 1/2.
Constraints
-2^31 <= val <= 2^31 - 1getRandomis only called when the set 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 12 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 (hash set, walk to a random position) | insert/remove O(1), getRandom O(n) | O(n) |
| Optimal (array + value-to-index map) | O(1) average for every operation | O(n) |
1Brute force (hash set, walk to a random position)
insert/remove O(1), getRandom O(n)A hash set has no index, so reaching the k-th element means walking up to n entries.O(n)The set holds every stored value.Store the values in a hash set. Insert and remove are O(1). For getRandom, pick a random position k and walk the set's iterator k steps.
- insert: add to the set and return whether it was new.
- remove: delete from the set and return whether it was there.
- getRandom: k = random index below the size; step through the set k times and return that element.
class RandomizedSet {
private final Set<Integer> set = new HashSet<>();
private final Random rnd = new Random();
public boolean insert(int val) { return set.add(val); }
public boolean remove(int val) { return set.remove(val); }
public int getRandom() {
int k = rnd.nextInt(set.size());
Iterator<Integer> it = set.iterator();
for (int i = 0; i < k; i++) it.next();
return it.next();
}
}import random
class RandomizedSet:
def __init__(self):
self.s = set()
def insert(self, val: int) -> bool:
if val in self.s:
return False
self.s.add(val)
return True
def remove(self, val: int) -> bool:
if val not in self.s:
return False
self.s.remove(val)
return True
def getRandom(self) -> int:
k = random.randrange(len(self.s))
for i, x in enumerate(self.s):
if i == k:
return xclass RandomizedSet {
unordered_set<int> s;
public:
bool insert(int val) { return s.insert(val).second; }
bool remove(int val) { return s.erase(val) > 0; }
int getRandom() {
int k = rand() % s.size();
auto it = s.begin();
advance(it, k);
return *it;
}
};class RandomizedSet {
constructor() {
this.s = new Set();
}
insert(val) {
if (this.s.has(val)) return false;
this.s.add(val);
return true;
}
remove(val) {
return this.s.delete(val);
}
getRandom() {
let k = Math.floor(Math.random() * this.s.size);
for (const x of this.s) {
if (k-- === 0) return x;
}
}
}2Optimal (array + value-to-index map)
O(1) average for every operationEach operation does a constant number of map lookups and array writes at known positions.O(n)The array and the map each hold one entry per stored value.Keep the values packed in an array so a random index picks a uniform random value, and keep a map from each value to its index. To remove a value from the middle, copy the last value into its slot, update that value's index in the map, and pop the end of the array. Nothing ever shifts.
- insert: if val is in the map return false; otherwise append it to the array, store its index, return true.
- remove: if val is missing return false. Let i = its index and last = the array's last value; put last at i, set map[last] = i, pop the array, delete val from the map, return true.
- getRandom: return array[random index below the array's size].
class RandomizedSet {
private final List<Integer> vals = new ArrayList<>();
private final Map<Integer, Integer> pos = new HashMap<>();
private final Random rnd = new Random();
public boolean insert(int val) {
if (pos.containsKey(val)) return false;
pos.put(val, vals.size());
vals.add(val);
return true;
}
public boolean remove(int val) {
Integer i = pos.get(val);
if (i == null) return false;
int last = vals.get(vals.size() - 1);
vals.set(i, last);
pos.put(last, i);
vals.remove(vals.size() - 1);
pos.remove(val);
return true;
}
public int getRandom() {
return vals.get(rnd.nextInt(vals.size()));
}
}import random
class RandomizedSet:
def __init__(self):
self.vals = []
self.pos = {} # value -> index in vals
def insert(self, val: int) -> bool:
if val in self.pos:
return False
self.pos[val] = len(self.vals)
self.vals.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.pos:
return False
i = self.pos[val]
last = self.vals[-1]
self.vals[i] = last
self.pos[last] = i
self.vals.pop()
del self.pos[val]
return True
def getRandom(self) -> int:
return self.vals[random.randrange(len(self.vals))]class RandomizedSet {
vector<int> vals;
unordered_map<int, int> pos; // value -> index in vals
public:
bool insert(int val) {
if (pos.count(val)) return false;
pos[val] = vals.size();
vals.push_back(val);
return true;
}
bool remove(int val) {
auto it = pos.find(val);
if (it == pos.end()) return false;
int i = it->second;
int last = vals.back();
vals[i] = last;
pos[last] = i;
vals.pop_back();
pos.erase(val);
return true;
}
int getRandom() {
return vals[rand() % vals.size()];
}
};class RandomizedSet {
constructor() {
this.vals = [];
this.pos = new Map(); // value -> index in vals
}
insert(val) {
if (this.pos.has(val)) return false;
this.pos.set(val, this.vals.length);
this.vals.push(val);
return true;
}
remove(val) {
if (!this.pos.has(val)) return false;
const i = this.pos.get(val);
const last = this.vals[this.vals.length - 1];
this.vals[i] = last;
this.pos.set(last, i);
this.vals.pop();
this.pos.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 returns false and changes nothing
- Removing a value that is not present returns false
- Removing the value stored in the last slot of the array
- Removing until one value is left, then calling getRandom
- Removing a value and inserting it again
Hints
Hint 1
A hash set gives O(1) insert and remove, but cannot pick a random element in O(1). An array can pick a random index in O(1), but cannot remove from the middle cheaply.
Hint 2
Use both: an array of the values and a map from value to its index in the array.
Hint 3
To remove from the middle of the array in O(1), move the last element into the hole and pop the end.
FAQ
What is the best time complexity for Insert Delete GetRandom O(1)?
Optimal (array + value-to-index map) runs in O(1) average for every operation time and O(n) extra space. Each operation does a constant number of map lookups and array writes at known positions.
Which pattern does Insert Delete GetRandom O(1) use?
It is a design data structures problem that uses the hash map + array pattern. Other problems with the same pattern: Logger Rate Limiter, Insert Delete GetRandom O(1) - Duplicates allowed, Design Parking System.
Is there a brute force solution for Insert Delete GetRandom O(1)?
Yes. Brute force (hash set, walk to a random position) takes insert/remove O(1), getRandom O(n) time and O(n) space. Store the values in a hash set.
Which edge cases should I test for Insert Delete GetRandom O(1)?
Inserting a value that is already present returns false and changes nothing; Removing a value that is not present returns false; Removing the value stored in the last slot of the array; Removing until one value is left, then calling getRandom; Removing a value and inserting it again.