O(1) Random Insert / Delete

$O(1)$ Insert, Delete, and GetRandom

This design problem is a classic interview puzzle because each operation seems to pull in a different direction. Arrays give you $O(1)$ random access by index but $O(n)$ deletion. Hashmaps give you $O(1)$ lookup and deletion but no notion of position, so you cannot select a random element uniformly. The trick is combining both structures so each compensates for the other's weakness.

The Design Challenge

Think about what each operation needs:

• Insert: easy with either structure. Arrays append in $O(1)$. Hashmaps insert in $O(1)$.
• Delete: hard with arrays. To remove an arbitrary element you'd have to shift everything after it, which is $O(n)$.
• GetRandom: impossible with hashmaps alone. You cannot index into a hashmap by position, so picking a uniformly random element would require collecting all keys first.

The solution is to use an array as the primary storage (enabling index-based random access) and a hashmap that maps each value to its index in the array (enabling $O(1)$ lookup for deletion).

The Swap-to-End Trick

The breakthrough insight is that deleting from the end of an array is $O(1)$. So to delete an arbitrary element at index i, swap it with the last element, update the last element's recorded index in the hashmap, then pop from the end. The evicted element is gone; the swapped element is now at index i with its hashmap entry corrected.

Walked Example

Start with an empty set.

• insert(10): array: [10], map: {10: 0}; returns True
• insert(20): array: [10, 20], map: {10: 0, 20: 1}; returns True
• insert(30): array: [10, 20, 30], map: {10: 0, 20: 1, 30: 2}; returns True
• remove(10): 10 is at index 0; last element is 30 (index 2). Swap: array becomes [30, 20, 10], then pop: [30, 20]. Update map: {30: 0, 20: 1}, delete key 10. Returns True.
• getRandom(): picks randomly from [30, 20]; each has 50% probability.

Notice that after the swap, we only need to update the hashmap entry for the element that moved (30), not for the element we removed. That keeps deletion $O(1)$.

The Implementation

For LeetCode 380, we combine these ideas into the following solution.

import random

class RandomizedSet:
    def __init__(self):
        self.vals = []       # array of values
        self.idx = {}        # value -> index in vals

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

    def remove(self, val: int) -> bool:
        if val not in self.idx:
            return False
        i = self.idx[val]
        last = self.vals[-1]
        # Move last element into the slot being vacated
        self.vals[i] = last
        self.idx[last] = i
        # Remove the now-duplicate tail
        self.vals.pop()
        del self.idx[val]
        return True

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

One subtle edge case: if val is the last element in the array, i == len(self.vals) - 1 and last == val. The swap is a no-op (you're writing val back into its own slot and updating idx[val] = i, which is about to be deleted anyway). Then vals.pop() and del self.idx[val] clean up correctly. No special case needed.

Handling Duplicates

The standard RandomizedSet rejects duplicate insertions. A variant (LC 381) allows duplicates and must still return a uniformly random element. The structure changes slightly: instead of mapping value -> single index, the hashmap maps value -> set of indices.

import random
from collections import defaultdict

class RandomizedCollection:
    def __init__(self):
        self.vals = []
        self.idx = defaultdict(set)   # value -> set of indices

    def insert(self, val: int) -> bool:
        already_present = bool(self.idx[val])
        self.idx[val].add(len(self.vals))
        self.vals.append(val)
        return not already_present

    def remove(self, val: int) -> bool:
        if not self.idx[val]:
            return False
        # Prefer removing the tail position when val itself sits there.
        # This avoids a self-swap that would corrupt the index set.
        last_idx = len(self.vals) - 1
        if last_idx in self.idx[val]:
            remove_idx = last_idx
        else:
            remove_idx = next(iter(self.idx[val]))
        last = self.vals[last_idx]
        # Swap the tail into the vacated slot and rewire indices
        self.vals[remove_idx] = last
        self.idx[val].discard(remove_idx)
        self.idx[last].discard(last_idx)
        if remove_idx != last_idx:
            self.idx[last].add(remove_idx)
        self.vals.pop()
        return True

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

Two subtleties make this tricky. First, if val itself appears at the tail, we deliberately pick that tail index for removal. Otherwise the "swap" would write val over a different occurrence of val and then we would lose track of which set membership to delete. Second, the order of set updates is: discard the chosen index from idx[val], discard the tail index from idx[last], then add the new position to idx[last] only if it actually moved. This handles the val == last case correctly: both discards apply to the same set and remove different indices, and the conditional add prevents reinserting the dead position.

Complexity

All three operations, insert, remove, and getRandom, run in $O(1)$ average time. random.choice on a list is $O(1)$ because Python lists support index access in constant time. Space is $O(n)$ where n is the number of elements currently in the collection.

This pattern generalises: any time you need uniform random sampling from a dynamic collection, reach for the array-plus-hashmap combo with the swap-to-end delete trick.

Recognizing this pattern

You're probably looking at array + index hashmap when:

• The problem demands O(1) average insert, remove, and getRandom on a dynamic collection.
• You need uniform random sampling from a set whose elements change over time.
• A plain hashset gives O(1) insert/remove but no O(1) random pick; a list gives random pick but O(n) remove.
• The fix involves swapping the to-be-removed element with the last array entry.

Common templates:

• Set with O(1) random: array of values plus value-to-index map; remove via swap-with-last and pop. Example: Insert Delete GetRandom O(1).
• Multiset with O(1) random: same idea, but the map points to a set of indices per value. Example: Insert Delete GetRandom O(1) - Duplicates allowed.
• Blacklisted random pick: remap blacklisted indices into the valid range via a hashmap. Example: Random Pick with Blacklist.
• Weighted random with updates: array of cumulative weights with binary search; pair with index map when weights mutate. Example: Random Pick with Weight.