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 design problem with no classical brute force. Start with a single container and see 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

Pair the two containers so each one’s strength 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 of the list is the one remaining O(n) cost. Avoid it: overwrite the target slot with the last element (a set has no order to preserve), fix that element’s index in the dict, and pop the tail in O(1).

The remove step is the core of the design:

flowchart LR
    A["Look up i = index_of[val]"] --> B["Copy last element<br/>vals[i] = vals[-1]"]
    B --> C["Update moved element<br/>index_of[last] = i"]
    C --> D["Pop the tail<br/>vals.pop()"]
    D --> E["Delete key<br/>del index_of[val]"]

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 shows the core mechanism: the gap at index 0 is filled by the tail element in O(1), and the dict is updated 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

• Removing the tail element itself: if val is the last element, the swap writes index_of[last] = i for the element being deleted. The code above handles this because last == val in that case, so the subsequent del index_of[val] removes the key. Reorder those two steps and the key is left behind.
• Deleting with vals.remove(val) or vals.pop(i) for middle i — both are O(n) shifts and defeat the design.
• 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 construction for “O(1) everything” set designs: the array gives O(1) uniform random access, the map gives O(1) location, and swap-with-last turns any deletion into a tail deletion when order does not matter. Reuse it whenever a design problem needs O(1) removal from an indexable collection.