Insert Delete GetRandom O(1) - Duplicates Allowed

Insert Delete GetRandom O(1) is a classic design problem: build a collection where adding, removing, and picking a uniformly random element are all O(1). The duplicates allowed twist is what makes it interesting — the same value can appear many times, so a single value cannot map to a single position any more.

The slow way first

A plain list gives O(1) getRandom (pick a random index) and O(1) insert (append), but remove(val) is O(n): you have to scan for the value and then shift everything after it down. A linked list or a balanced tree fixes some of those but breaks O(1) random access. We want all three operations O(1).

The question to ask: what extra bookkeeping lets me delete from the middle of an array without shifting?

The idea: a list plus a map of index sets

Keep two structures. A list vals holds the actual values — that gives O(1) getRandom via a random index. A map idx sends each value to the set of indices where it currently lives — that gives O(1) membership and lets us find some position of a value instantly.

To delete in O(1) without shifting: swap the victim with the last element, then pop the tail. Popping the end of a list is O(1). After the swap we fix the moved element's index in its set.

Using a set of indices (not a list) is what keeps duplicates honest: adding and discarding a specific index is O(1), so the swap-with-last trick still works when a value appears many times.

Walk through it

Step through the animation on [4, 7, 7, 4] with remove(7). We pull index 1 out of idx[7], copy the last value 4 (at index 3) into slot 1, update idx[4] to swap 3 for 1, then pop the tail. The result is [4, 4, 7] — one 7 removed, every other index still consistent with the map.

Pseudocode

insert(val):
    add (current length) to idx[val]'s set
    append val to the list
    return True if this was the first copy of val
 
remove(val):
    if idx[val] is empty: return False
    i = pop any index from idx[val]
    last = last index of the list
    move the last value into slot i (copy it over)
    in that value's set: add i, discard last
    pop the last element off the list
    return True
 
getRandom():
    return list[random index]

The Python solution

class RandomizedCollection:
    def __init__(self):
        self.vals = []
        self.idx = defaultdict(set)
 
    def insert(self, val):
        self.idx[val].add(len(self.vals))
        self.vals.append(val)
        return len(self.idx[val]) == 1
 
    def remove(self, val):
        if not self.idx[val]:
            return False
        i = self.idx[val].pop()
        last = len(self.vals) - 1
        last_val = self.vals[last]
        self.vals[i] = last_val
        self.idx[last_val].add(i)
        self.idx[last_val].discard(last)
        self.vals.pop()
        return True

• vals is the flat list of values; idx maps each value to the set of indices where it appears.
• insert records the new index before appending, and returns whether this is the first copy of val.
• In remove, i = self.idx[val].pop() grabs any position of val — a set pop is O(1).
• The swap is the trick: self.vals[i] = last_val overwrites the hole with the last value so we never shift.
• We then add(i) and discard(last) on the moved value's set so its bookkeeping stays correct.
• discard (not remove) is safe even when i == last, the edge case where the victim already was the last element.

Complexity

Every operation is average O(1), and we use O(n) extra space for the index map. The whole design rests on one move: deleting from the middle of an array is O(1) if you swap with the last element first.

When this pattern shows up

Practice