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 that holds a set of whole numbers, with no value stored twice. Each of its three operations must take O(1) time on average, a fixed amount of work however many values the set holds:

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
Solution

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) returns true, and remove(2) returns false, because 2 is not there yet. Then insert(2) returns true, so the set holds 1 and 2, and getRandom() may return either. Next 1 is removed, a second insert(2) returns false because 2 is already there, and the last getRandom() can only return 2.

Java has two structures that each do part of this. A HashSet adds, removes and checks a value in O(1) on average, but its values have no numbered positions, so there is nothing to pick at random by number. An ArrayList has numbered positions, so a random position from 0 to size - 1 gives a fair pick in one step. But finding a value in the list means looking through it, and removing from the middle moves every later value one place left.

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.

After inserting 10, 20 and 30, the values list is 10, 20, 30 and the indexOf map gives 10 at index 0, 20 at 1, 30 at 2. After remove(10), the last value 30 moves into slot 0, the list is 30, 20, and the map gives 30 at 0 and 20 at 1.

On the left, after insert(10), insert(20) and insert(30), the list named values holds 10, 20 and 30 at index 0, 1 and 2. The map named indexOf records the same positions. On the right, remove(10) has run. The map said 10 sat at index 0, so the last value, 30, was moved into slot 0, the position 10 had left, and the slot at index 2 was dropped from the end. The orange row of the map shows 30's new index.

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 makes its pick fair and its output repeatable.

Keeping the list and the map in step

What does insert have to update? A new value always goes at the end of values, so its index is the list's size just before the add. The method writes that number into indexOf and then appends the value. A value already in indexOf is in the set, so insert returns false and changes nothing.

Removing by swapping with the last value

Why not just call values.remove(index)? It does remove the value, but every later value shifts one place left, one move per value after it. It also leaves the map wrong: in the picture, 30 would slide to index 1 while indexOf still says 2.

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 getRandom give every value the same chance? Because the list has no gaps, every index from 0 to size - 1 holds a value. Picking one of those indexes with random.nextInt(values.size()), where each index is equally likely, picks each value equally often.

A Random object built with a fixed start number, called a seed, returns the same sequence of picks on every run. The class takes the seed in its constructor, so the program's printed output comes out the same each time. To check fairness, main also counts the results of many picks.

Java Solution

The class has four parts:

  • The list values, an ArrayList, holds the set's values with no gaps, for getRandom to pick from.
  • The map indexOf, a HashMap, gives each value's index in values. It lets insert spot repeats and remove find the slot to fill.
  • The method remove takes the last value off values, keeps it in last, and writes it into the removed value's index i when i is still inside the shorter list.
  • The field random is a Random built from the seed passed to the constructor, so runs repeat exactly.

The main method runs Example 1, then inserts 10, 20 and 30 and removes 10 twice, as in the picture, counts 30,000 random picks, and finally removes every value and inserts one back.

Java
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:

Output
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 2. With seed 7 the first getRandom() picked 2; another seed may pick 1, which the example also allows. The line starting remove(10) true matches the right half of the picture: the list is [30, 20] and the map gives 30 index 0. A HashMap prints its entries in its own order, so {20=1, 30=0} lists 20 first. The second remove(10) returns false and changes nothing.

Out of 30,000 picks from [30, 20], 20 came up 15,092 times and 30 came up 14,908 times, both close to half. The last three lines cover removing the last value: remove(30) leaves both structures empty, because 30 was the end of the list and nothing had to move, and 30 can then be inserted again.

The swap is what keeps the map correct. A version that calls values.remove(i) at the removed value's own index, after inserting 10, 20 and 30 and removing 10, holds the list [20, 30] while the map still gives 30 index 2. Calling remove(30) on that version throws java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2.

The original implementation, InsertDeleteGetRandom.java, is on GitHub.

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 insert and remove each make two HashMap calls, constant on average, and change the list only at its end or at the known index i. Adding at the end of an ArrayList is constant on average too, which the ArrayList documentation calls amortized constant time. The method getRandom draws one index and reads that slot.
  • Space: O(n) for n values in the set, because each value sits once in values and once as a key in indexOf.

When the same value may be stored more than once, see Randomized Collection.