381. Insert Delete GetRandom O(1) - Duplicates allowed

Problem¶

Design a multiset supporting average \(O(1)\) operations:

insert(val): add one occurrence; return whether val was previously absent.
remove(val): remove one occurrence if present; return whether removal succeeded.
getRandom(): sample uniformly among occurrences; called only when nonempty.

Operation       Return       Multiset
insert(1)       True         [1]
insert(1)       False        [1, 1]
insert(2)       True         [1, 1, 2]
getRandom()     1 or 2       P(1) = 2/3, P(2) = 1/3
remove(1)       True         [1, 2]
remove(3)       False        [1, 2]

class RandomizedCollection:
    def __init__(self):
        pass

    def insert(self, val: int) -> bool:
        pass

    def remove(self, val: int) -> bool:
        pass

    def getRandom(self) -> int:
        pass

Key trick¶

Store occurrences in a dense list and map each value to its set of indices; delete by replacing an occurrence with the last element.

Trap¶

Update both affected index sets correctly, especially when the removed value equals the last value; sample occurrences, not distinct values.

Why is it interesting?¶

It combines constant-time deletion with frequency-weighted sampling without maintaining explicit probabilities.

Python solution¶

import random


class RandomizedCollection:
    def __init__(self):
        self.values = []
        self.indices = {}

    def insert(self, val: int) -> bool:
        is_new = val not in self.indices
        self.indices.setdefault(val, set()).add(len(self.values))
        self.values.append(val)
        return is_new

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

        idx = self.indices[val].pop()
        last_idx = len(self.values) - 1
        last_val = self.values[-1]

        if idx != last_idx:
            # Move the last occurrence into the gap, even if last_val == val.
            self.values[idx] = last_val
            self.indices[last_val].remove(last_idx)
            self.indices[last_val].add(idx)

        self.values.pop()
        if not self.indices[val]:
            del self.indices[val]

        return True

    def getRandom(self) -> int:
        # Uniform positions automatically weight values by their frequency.
        return random.choice(self.values)

Time: Average amortized \(O(1)\) per operation.

Space: \(O(n)\) for \(n\) stored occurrences.

Comment on my solution¶

Your solution is correct and has the required complexity, including when last_val == val: deleting the mapping before updating is safe because it cannot be empty when another occurrence must move.

The main simplification is returning len(self.index[val]) == 1 directly from insert; moving empty-set cleanup after index updates also makes remove easier to reason about.

# Ideas:
# - similar to the problem "Insert Delete GetRandom O(1)" no duplicate
#   - instead of using a index of value to index, we'll keep an Index
#     of value to set of indices

import random

# WORKS
class RandomizedCollection:

    def __init__(self):
        self.values = []
        self.index = {} # map value -> {set of indices}

    def insert(self, val: int) -> bool:
        self.index.setdefault(val, set()).add(len(self.values))
        self.values.append(val)
        if len(self.index[val]) > 1:
            return False
        return True

    def remove(self, val: int) -> bool:
        if val not in self.index:
            return False
        remove_idx = self.index[val].pop()
        last_idx = len(self.values) - 1
        last_val = self.values[-1]
        self.values[remove_idx] = last_val
        self.values.pop()
        if not self.index[val]:
            del self.index[val]
        if last_idx != remove_idx:
            self.index[last_val].remove(last_idx)
            self.index[last_val].add(remove_idx)
        return True

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