#380 Insert Delete GetRandom O(1)

frequently reported atBloomberg Uber LinkedIn ByteDance / TikTok Apple Amazon

the problem

In plain words

Build an integer set called RandomizedSet. insert(val) adds val if it is missing and tells you whether it was added. remove(val) deletes val if it is there and tells you whether it was deleted. getRandom() returns one of the values stored right now, each with the same chance; it is only called when the set is not empty. All three calls must take O(1) time on average.

in insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom()

out true, false, true, 1 or 2, true, false, 2

remove(2) fails because 2 isn't stored yet. After remove(1) only 2 is left, so the last getRandom must return 2.

−2³¹ ≤ val ≤ 2³¹ − 1
At most 2·10⁵ calls in total
getRandom is only called when the set holds at least one value

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternHashMap + array (O(1) random access)

where this runsGCC's Briggs–Torczon sparse sets pair a dense array of members with an index for each member, and delete by moving the last member into the hole — the same design, with an array where we use a HashMap.

A random pick needs an index, so keep the values in an ArrayList. A delete must not search or shift, so keep a HashMap value → index and fill the hole with the last element — removing the end of an ArrayList is free.

solutions

From brute force to optimal

Keep the values in a list; getRandom picks a random index.

insert: contains scans the list; append if the value is missing.
remove: remove(Integer.valueOf(val)) finds the value and shifts the rest left.
getRandom: items.get(random.nextInt(items.size())).

timeinsert/remove O(n), getRandom O(1)

contains and remove both walk the list, and remove also shifts every later element.

spaceO(n)

One list entry per value.

javajava.util.* · java.util.function.*

1// On LeetCode, name this class RandomizedSet.2class RandomizedSetList {3    private final List<Integer> items = new ArrayList<>();4    private final Random random = new Random();5 6    public boolean insert(int val) {7        if (items.contains(val)) return false; // walks the whole list: O(n)8        items.add(val);9        return true;10    }11 12    public boolean remove(int val) {13        return items.remove(Integer.valueOf(val)); // finds val (O(n)), then shifts everything after it14    }15 16    public int getRandom() {17        return items.get(random.nextInt(items.size())); // a random index: O(1)18    }19}

A HashSet makes insert and remove O(1) — but it has no index to pick from.

insert / remove: set.add(val) / set.remove(val), O(1) on average.
getRandom: draw r = random.nextInt(size), then walk the set's iterator r steps.

timeinsert/remove O(1) avg, getRandom O(n)

A set can't jump to its k-th element; the walk visits up to n entries.

spaceO(n)

One set entry per value.

javajava.util.* · java.util.function.*

1// On LeetCode, name this class RandomizedSet.2class RandomizedSetHash {3    private final Set<Integer> items = new HashSet<>();4    private final Random random = new Random();5 6    public boolean insert(int val) {7        return items.add(val); // O(1) average8    }9 10    public boolean remove(int val) {11        return items.remove(val); // O(1) average12    }13 14    public int getRandom() {15        int skip = random.nextInt(items.size()); // a set has no index, so walk to the chosen position16        for (int x : items) {17            if (skip-- == 0) return x; // up to n steps: O(n)18        }19        throw new IllegalStateException("getRandom on an empty set");20    }21}

The list gives O(1) random access; the map answers "where is val?" in O(1). Delete by moving the last element into the hole.

insert: if the map has val, return false. Otherwise map val → size, then append val.
remove: i = map.get(val) (null → return false); last = the list's last element.
Copy last into slot i and set map[last] = i; then remove the list's end and remove val from the map.
getRandom: values.get(random.nextInt(values.size())).

timeO(1) average per call

HashMap operations are O(1) on average; set(i, …) and removing the last slot shift nothing; ArrayList.add is O(1) amortized.

spaceO(n)

Each value is stored once in the list and once as a map key.

javajava.util.* · java.util.function.*

1class RandomizedSet {2    private final List<Integer> values = new ArrayList<>();        // the elements, in any order3    private final Map<Integer, Integer> indexOf = new HashMap<>(); // value → its index in values4    private final Random random = new Random();5    // invariant: values.get(indexOf.get(v)) == v for every v in the set6 7    public boolean insert(int val) {8        if (indexOf.containsKey(val)) return false;9        indexOf.put(val, values.size()); // it will sit at the end10        values.add(val);11        return true;12    }13 14    public boolean remove(int val) {15        Integer i = indexOf.get(val);16        if (i == null) return false;17        int last = values.get(values.size() - 1);18        values.set(i, last);              // the last element fills the hole19        indexOf.put(last, i);             // and the map learns its new index20        values.remove(values.size() - 1); // removing the end shifts nothing21        indexOf.remove(val);              // last, so it also works when val was the last element22        return true;23    }24 25    public int getRandom() {26        return values.get(random.nextInt(values.size())); // every index equally likely27    }28}

sim

Dry run

loading simulation…

javajava.util.* · java.util.function.*

1class RandomizedSet {2    private final List<Integer> values = new ArrayList<>();        // the elements, in any order3    private final Map<Integer, Integer> indexOf = new HashMap<>(); // value → its index in values4    private final Random random = new Random();5    // invariant: values.get(indexOf.get(v)) == v for every v in the set6 7    public boolean insert(int val) {8        if (indexOf.containsKey(val)) return false;9        indexOf.put(val, values.size()); // it will sit at the end10        values.add(val);11        return true;12    }13 14    public boolean remove(int val) {15        Integer i = indexOf.get(val);16        if (i == null) return false;17        int last = values.get(values.size() - 1);18        values.set(i, last);              // the last element fills the hole19        indexOf.put(last, i);             // and the map learns its new index20        values.remove(values.size() - 1); // removing the end shifts nothing21        indexOf.remove(val);              // last, so it also works when val was the last element22        return true;23    }24 25    public int getRandom() {26        return values.get(random.nextInt(values.size())); // every index equally likely27    }28}

in the room

How to say it in the interview

talk track

Say the target: three methods, each O(1) on average.
Rule out the easy ones aloud: a list makes remove O(n); a set makes getRandom O(n). So I need an index and a lookup.
State the invariant: values.get(indexOf.get(v)) == v for every v in the set.
Explain remove with the hole: copy the last element into it, fix that element's index, drop the end.
Dry-run removing the last element and removing the only element — both must work.

traps

Forgetting indexOf.put(last, i): the moved value keeps a stale index.
Removing val from the map before re-indexing last: when val is the last element, the put adds val back.
values.remove(val) with an int removes by index, not by value.

what they ask next

Follow-ups

Duplicates allowed (LC 381)?

Map each value to a set of its indices. remove takes any index of val, moves the last element there and fixes that element's index set. getRandom stays a random list index, so a value with more copies is more likely — exactly what LC 381 asks.

Make it thread-safe?

Mark the three methods synchronized: each one changes the list and the map together. A ConcurrentHashMap alone would not keep the two consistent.

Pick by weight instead of uniformly?

That's Random Pick with Weight (LC 528): prefix sums of the weights, a random ticket, and a binary search for the ticket's index.

before you submit

Edge cases to test

Removing the element that is last in the list: the copy does nothing, and the order of the map updates matters.
Removing the only element, then inserting it again.
insert of a value that is already there returns false and changes nothing.
Values outside −128…127: compare Integers by value, never with ==.

practise next