Insert Delete GetRandom O(1)

The natural first move is to lean on Python’s set. It stores unique values in a hash table, so insert, remove, and the membership test behind both are average O(1). The only operation it cannot serve directly is getRandom: a set is unordered and exposes no index you can sample. To draw uniformly you have to materialize the elements into a sequence and then pick one — and that copy is O(n) per call.

import random

class RandomizedSet:
    def __init__(self):
        self.items: set[int] = set()

    def insert(self, val: int) -> bool:
        if val in self.items:
            return False
        self.items.add(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.items:
            return False
        self.items.remove(val)
        return True

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

The set’s own operations are constant time, but tuple(self.items) walks every element on each getRandom, so this is O(n) exactly where the problem demands O(1). That copy is the cost to remove, and the next design removes it.

Keep two structures that describe the same set:

• values — a dynamic array holding every element exactly once, packed with no holes.
• index — a dictionary mapping each value to the slot it occupies in values.

The array supplies the position the set was missing: getRandom just reads values[random index]. Because the array is packed, every element sits in exactly one slot, so every element has the same 1 / n chance of being drawn — the uniformity is a direct consequence of there being no holes. The dictionary supplies the speed the array was missing: insert checks membership in O(1).

insert is the easy half — if the value is already in index, return false; otherwise append it at the end of values (no shifting) and record its slot. getRandom is one indexed read plus one hash lookup in the average case. The interesting half is remove.

Deleting the value at slot i cannot move the whole tail down — that is O(n). Instead, take the last element of values and overwrite slot i with it, update that element’s entry in index to point at i, then pop the tail off the array. The freed value’s own map entry is deleted last. This is a constant number of writes regardless of i, so remove is average O(1).

import random

class RandomizedSet:
    def __init__(self):
        self.index: dict[int, int] = {}   # value -> slot in values
        self.values: list[int] = []       # packed, no holes

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

    def remove(self, val: int) -> bool:
        if val not in self.index:
            return False
        i = self.index[val]
        last = self.values[-1]
        self.values[i] = last      # fill the hole with the last element
        self.index[last] = i       # its recorded slot moved
        self.values.pop()          # drop the tail (now duplicated at i)
        del self.index[val]        # forget the removed value
        return True

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

One edge case deserves attention: when the value being removed is itself the last element, then last equals val, the overwrite is a no-op, and the pop alone removes it. The code stays correct only because the write self.index[last] = i happens before del self.index[val] — if the deletion came first, this case would leave the map in an inconsistent state. That is the ordering the reference implementation depends on.

What to watch: every remove copies the last element into the deleted slot and rewrites that element’s map entry, so the array never grows a hole — and that is exactly what keeps getRandom uniform.

Complexity. insert performs one hash lookup, one dictionary insert, and one array append: average O(1). remove performs one lookup, at most two dictionary writes, one array write, and one pop: average O(1). getRandom performs one indexed read: O(1). The “average” qualifier is only about hash collisions inside the dictionary. Space is O(n) — the array and the map each hold the n elements once, and the array occupies a contiguous block because it never has gaps.