Insert Delete GetRandom O(1)
Medium ArrayList + HashMap
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Design a set that supports insert, remove and getRandom (each element equally likely), all in average O(1) time.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: a set where add, remove and "pick a random element" are all O(1).
Why this works: a list gives random access by index; a map gives value → index lookups. Remove becomes O(1) by moving the last element into the hole instead of shifting everything.
Example: insert 1, insert 2, insert 3, remove 1
list = [1, 2, 3], pos = {1:0, 2:1, 3:2}remove 1: last = 3 moves to index 0list = [3, 2], pos = {3:0, 2:1}getRandom picks index 0 or 1 → 3 or 2
✦Hints open one at a time
↗Approach
Store values in an ArrayList and a HashMap from value to its index in the list. Insert appends. Remove moves the last element into the removed slot, fixes its map entry, and deletes the tail. getRandom picks a random index.
</>Solution (Java)
import java.util.*;
class RandomizedSet {
private final List<Integer> list = new ArrayList<>();
private final Map<Integer, Integer> pos = new HashMap<>(); // value -> index in list
private final Random rand = new Random();
public boolean insert(int val) {
if (pos.containsKey(val)) return false;
pos.put(val, list.size());
list.add(val);
return true;
}
public boolean remove(int val) {
Integer i = pos.get(val);
if (i == null) return false;
int last = list.get(list.size() - 1);
list.set(i, last); // move last element into the hole
pos.put(last, i);
list.remove(list.size() - 1);
pos.remove(val); // done after put, so it also works when val == last
return true;
}
public int getRandom() {
return list.get(rand.nextInt(list.size()));
}
}!Common mistake
Forgetting to update the moved element's index in the map, or removing the map entry before the swap when the removed value is itself the last element.
- Time: O(1) average for every operation.
- Space: O(n).
