Insert Delete GetRandom O(1)

Problem

Design a set-like data structure RandomizedSet supporting three operations, each in average O(1) time:

• insert(val) — add val if absent; return True if it was added, False if it was already present.
• remove(val) — delete val if present; return True if it was removed, False if it wasn’t there.
• getRandom() — return a uniformly random element from the current set (each element equally likely). It is guaranteed the set is non-empty when this is called.

The challenge is that no single standard container gives you all three: a hash set has O(1) insert/remove but no O(1) uniform sampling; an array samples in O(1) but removes in O(n).

Examples

Example 1:

insert(1) -> True    # {1}
remove(2) -> False   # 2 not present
insert(2) -> True    # {1, 2}
getRandom() -> 1 or 2, each with probability 1/2
remove(1) -> True    # {2}
insert(2) -> False   # already there
getRandom() -> 2     # only element left

Example 2: insert(5) -> True, insert(5) -> False — a duplicate insert reports failure and the set still holds one 5.

Constraints

• -2^31 <= val <= 2^31 - 1
• Up to 2 * 10^5 total calls to the three operations.
• All three operations must run in average O(1).

The call volume means any O(n) operation (linear search, list remove) turns the worst case quadratic.

Think about it first

TL;DR

Dynamic array + hash map with swap-to-tail deletion — O(1) average per operation, O(n) space.

Approach 1 — Naive design (single container)

This is a pure design problem, so there is no classical brute force — the ladder starts at the “one container” design and shows where it breaks.

Back the set with just a Python list: insert appends after a membership scan, remove scans and deletes, getRandom picks a random index.

import random


class RandomizedSet:
    def __init__(self) -> None:
        self.vals: list[int] = []

    def insert(self, val: int) -> bool:
        if val in self.vals:          # O(n) scan
            return False
        self.vals.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.vals:      # O(n) scan
            return False
        self.vals.remove(val)         # O(n) shift
        return True

    def getRandom(self) -> int:
        return random.choice(self.vals)

Complexity: getRandom O(1); insert/remove O(n) each. With 2·10^5 operations, adversarial inserts/removes cost ~10^10 element touches. (A hash-set-only design has the mirrored flaw: O(1) insert/remove, but uniform getRandom requires materializing the elements, O(n) per call.)

Approach 2 — Array + hash map, swap-with-last deletion

The insight: pair the two containers so each covers the other’s weakness. The list stores values compactly so random.choice works; the dict maps each value to its list index so membership and location are O(1). Deletion from the middle is the one remaining O(n) hole — close it by not deleting from the middle: overwrite the doomed slot with the last element (a set has no order to preserve), fix that element’s index in the dict, and pop the tail, which is O(1).

import random


class RandomizedSet:
    def __init__(self) -> None:
        self.vals: list[int] = []          # compact value storage
        self.index_of: dict[int, int] = {} # value -> position in vals

    def insert(self, val: int) -> bool:
        if val in self.index_of:
            return False
        self.index_of[val] = len(self.vals)
        self.vals.append(val)
        return True

    def remove(self, val: int) -> bool:
        i = self.index_of.get(val)
        if i is None:
            return False
        last = self.vals[-1]
        self.vals[i] = last        # move tail into the hole
        self.index_of[last] = i    # tail's new address
        self.vals.pop()            # O(1) tail removal
        del self.index_of[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.vals)

Walkthrough of Example 1:

1. insert(1): 1 unseen → vals = [1], index_of = {1: 0} → True.
2. remove(2): 2 not in dict → False.
3. insert(2): → vals = [1, 2], index_of = {1: 0, 2: 1} → True.
4. getRandom(): uniform over [1, 2] — each with probability 1/2. ✓
5. remove(1): i = 0; last = 2; write 2 into slot 0 → vals = [2, 2]; index_of[2] = 0; pop tail → vals = [2]; delete key 1 → index_of = {2: 0} → True.
6. insert(2): 2 already keyed → False.
7. getRandom(): only 2 remains → returns 2. ✓

Step 5 is the whole trick: the “hole” at index 0 is plugged by the tail element in O(1), and the dict is repaired so the moved element stays findable.

Complexity: all three operations O(1) average (dict operations are amortized O(1); list append is amortized O(1)); space O(n).

getRandom is uniform because vals is always exactly the multiset-free list of current elements with no gaps, and random.choice picks an index uniformly. (random.choice(seq) is Python’s standard uniform pick over a sequence.)

Common pitfalls

• Updating the dict after popping when removing the last element itself: if val is the tail, the swap writes index_of[last] = i for the element being deleted — harmless only if you then del index_of[val]; get the order wrong and you resurrect the key. The code above handles it because last == val in that case and the subsequent del removes it.
• Deleting with vals.remove(val) or vals.pop(i) for middle i — both are O(n) shifts and silently forfeit the whole point.
• Forgetting to update the moved tail element’s index in the dict — later removals of that element then corrupt an unrelated slot.
• Sampling with random.choice(list(self.index_of)) — building the list is O(n) per call.

Pattern takeaway

The array+hashmap pair is the standard recipe for “O(1) everything” set designs: the array gives O(1) uniform random access, the map gives O(1) location, and swap-with-last converts any deletion into a tail deletion when order doesn’t matter. Reuse it whenever a design problem demands O(1) removal from an indexable collection.