Insert Delete Get Random O(1)
Build a set that adds, removes and picks a random value, each in constant time on average.
Write a class RandomizedSet
- The method
adds the value if it is not in the set yet, and returns true if it was added.insert(val) - The method
removes the value if it is in the set, and returns true if it was removed.remove(val) - The method
returns one of the values in the set, each with the same chance. The set is never empty when it is called.getRandom()
Example 1
Output: true, false, true, 1 or 2, true, false, 2
The Idea
Think of a raffle drum at a school fair. Tickets go in, a ticket can be taken back out by its number, and at the end someone draws one ticket, with every ticket in the drum equally likely to win. This class is that drum, holding numbers instead of tickets.
Walk through Example 1. First insert(1)remove(2)insert(2)getRandom()insert(2)getRandom()
Java has two structures that each do part of this. A HashSetArrayList
So can one class have both? Keep the values in a list, and next to it a map from each value to its position in the list, called its index. The map answers "where is 2?" in one step, and the list gives the random pick. One question is left: how to remove a value without shifting the rest. Look at the two halves of the picture.
On the left, after insert(10)insert(20)insert(30)valuesindexOfremove(10)
The order of the values in a set means nothing, so moving 30 to the front breaks no rule. That is the key insight: filling the gap with the last value turns a slow removal from the middle into a fast removal from the end.
Solution Approach
Three choices settle the class: how the two structures stay in step on insert, how remove fills the gap, and how getRandom
Keeping the list and the map in step
What does insertvaluesindexOfindexOfinsert
Removing by swapping with the last value
Why not just call values.remove(index)indexOf
The swap avoids both problems. Take the last value off the end of the list, which moves nothing else, and write it into the removed value's slot. Then one map entry, the moved value's, gets its new index. If the removed value was itself the last one, there is no gap to fill and nothing moves.
A fair and repeatable random pick
How does getRandomrandom.nextInt(values.size())
A Randommain
Java Solution
The class has four parts:
- The list
, anvalues , holds the set's values with no gaps, forArrayList to pick from.getRandom - The map
, aindexOf , gives each value's index inHashMap . It letsvalues spot repeats andinsert find the slot to fill.remove - The method
takes the last value offremove , keeps it invalues , and writes it into the removed value's indexlast wheni is still inside the shorter list.i - The field
is arandom built from the seed passed to the constructor, so runs repeat exactly.Random
The main
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
public class RandomizedSet {
private final List<Integer> values = new ArrayList<>(); // the values, no gaps
private final Map<Integer, Integer> indexOf = new HashMap<>(); // value -> index in values
private final Random random;
public RandomizedSet(long seed) {
random = new Random(seed); // fixed seed: same picks
}
public boolean insert(int val) {
if (indexOf.containsKey(val)) {
return false; // already in the set
}
indexOf.put(val, values.size()); // the next free index
values.add(val);
return true;
}
public boolean remove(int val) {
Integer i = indexOf.remove(val);
if (i == null) {
return false; // not in the set
}
int last = values.remove(values.size() - 1); // take off the end
if (i < values.size()) { // val was not the last one
values.set(i, last); // last value fills the gap
indexOf.put(last, i);
}
return true;
}
public int getRandom() {
return values.get(random.nextInt(values.size()));
}
public static void main(String[] args) {
RandomizedSet set = new RandomizedSet(7);
System.out.println(set.insert(1) + " " + set.remove(2) + " " + set.insert(2) + " "
+ set.getRandom() + " " + set.remove(1) + " " + set.insert(2) + " "
+ set.getRandom());
RandomizedSet s = new RandomizedSet(42);
s.insert(10);
s.insert(20);
s.insert(30);
System.out.println("after inserts: " + s.values + " " + s.indexOf);
System.out.println("remove(10) " + s.remove(10) + ": " + s.values + " " + s.indexOf);
System.out.println("remove(10) " + s.remove(10) + ": " + s.values + " " + s.indexOf);
Map<Integer, Integer> counts = new HashMap<>();
for (int k = 0; k < 30000; k++) {
counts.merge(s.getRandom(), 1, Integer::sum);
}
System.out.println("30000 picks: " + counts);
System.out.println("remove(20) " + s.remove(20) + ": " + s.values + " " + s.indexOf);
System.out.println("remove(30) " + s.remove(30) + ": " + s.values + " " + s.indexOf);
System.out.println("insert(30) " + s.insert(30) + ": " + s.values + " " + s.indexOf);
}
}
Running it prints:
true false true 2 true false 2
after inserts: [10, 20, 30] {20=1, 10=0, 30=2}
remove(10) true: [30, 20] {20=1, 30=0}
remove(10) false: [30, 20] {20=1, 30=0}
30000 picks: {20=15092, 30=14908}
remove(20) true: [30] {30=0}
remove(30) true: [] {}
insert(30) true: [30] {30=0}
Example 1 comes out as true false true 2 true false 2getRandom()remove(10) true[30, 20]HashMap{20=1, 30=0}remove(10)
Out of 30,000 picks from [30, 20]remove(30)
The swap is what keeps the map correct. A version that calls values.remove(i)[20, 30]remove(30)java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2
The original implementation,
Complexity
Every operation does a fixed number of map lookups and touches the list only at its end or at an index it already knows.
- Time: O(1) on average per call, because
andinsert each make tworemove calls, constant on average, and change the list only at its end or at the known indexHashMap . Adding at the end of ani is constant on average too, which theArrayList documentation calls amortized constant time. The methodArrayList draws one index and reads that slot.getRandom - Space: O(n) for n values in the set, because each value sits once in
and once as a key invalues .indexOf
When the same value may be stored more than once, see