Problem 40.5 · Designing Data StructuresMedium

Insert Delete GetRandom O(1)

PatternCombine Structures to Design Hash Map Lookup (Complement)

What it teaches: Array + index map, deleting by swapping with the last element.

Practise it on judges as “Insert Delete GetRandom O(1)”.

In plain words

You keep a bag of numbered balls and must add, remove and pick one at random, all instantly. A plain list makes picking at random easy (choose a random position), and a map from ball to position makes finding a ball easy. The clever part is removing: move the last ball into the hole left by the removed one, so the list never has gaps.

Return true or false for insert and remove (did the set change?), and a random element for getRandom. Example: insert(1), remove(2), insert(2), remove(1), insert(2), getRandom() → true, false, true, true, false, 2.

The problem

Design RandomizedSet with insert(val) and remove(val) (return whether the set changed) and getRandom() returning a uniformly random element, all in average O(1).

Example 1

Input: insert(1), remove(2), insert(2), remove(1), insert(2), getRandom()
Output: true, false, true, true, false, 2

Constraints

getRandom is only called when the set is non-empty

Pattern clues in the wording

→ O(1) random choice and O(1) delete

These clues point to Combine Structures to Design: Pair a hash map (fast lookup) with a list, heap or tree (fast ordering) to meet every operation's time limit.

Stuck? Take one hint at a time

RandomizedSet · starter

import java.util.*;

class RandomizedSet {
    public RandomizedSet() {}
    public boolean insert(int val) { return false; }
    public boolean remove(int val) { return false; }
    public int getRandom() { return 0; }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#	Input	Expected
1	ops = ["RandomizedSet","insert","remove","insert","remove","insert","getRandom"] args = [[],[1],[2],[2],[1],[2],[]] Only one element remains, so getRandom is deterministic here.	[null,true,false,true,true,false,2]

From slow to fast

Approaches

1. ArrayList + HashMap · O(1) average

ArrayList + HashMap

Time O(1) average Space O(n)

index[val] = position. remove: move the last value into val's position, update its index, remove the last slot.

▶ Dry run: List + index map, swap with last on removeinsert(1), remove(2), insert(2), remove(1), insert(2), getRandom()

index(map)

1: 0

returned(list)

true

Step 1/5insert(1): 1 is new, so record its position 0 and append it. Return true.

Approach 1

import java.util.*;

class RandomizedSet {
    private final List<Integer> vals = new ArrayList<>();
    private final Map<Integer, Integer> index = new HashMap<>();
    private final Random random = new Random();

    public RandomizedSet() {}

    public boolean insert(int val) {
        if (index.containsKey(val)) return false;
        index.put(val, vals.size());
        vals.add(val);
        return true;
    }

    public boolean remove(int val) {
        Integer i = index.remove(val);
        if (i == null) return false;
        int last = vals.remove(vals.size() - 1);
        if (i < vals.size()) { vals.set(i, last); index.put(last, i); }
        return true;
    }

    public int getRandom() { return vals.get(random.nextInt(vals.size())); }
}

Verdict: The standard trick.

Before you submit

Edge cases and common mistakes

Test these inputs

Removing the last element
Inserting a duplicate

Mistakes people make

Removing from the middle of the list (O(n)).

Interview

Follow-up questions

What if duplicates were allowed (RandomizedCollection)?

Command Palette

The problem

Approaches

ArrayList + HashMap

Edge cases and common mistakes

Follow-up questions