248. Design Randomized Set

Why this mechanism works

A list gives constant-time random indexing but slow arbitrary deletion. A dictionary locates any value's index. Delete by moving the list's final value into the removed slot, updating that moved value's index, then popping the last slot. Set semantics impose no order to preserve.

State and boundaries

values contains each member once, and positions[value] is exactly its current list index. Both structures represent the same membership after every operation.

Protocol

1. Insert absent values at the list end and map their index.
2. For removal locate the slot.
3. Move the final value into it and update that value's mapping.
4. Pop the list end and delete the removed mapping.
5. Choose a uniform random list entry.

Visualization

values [A,B,C], positions A:0 B:1 C:2
remove B -> move C into slot 1 -> [A,C]
repair C:1, delete B

Python implementation

import random
from structures import run_operations

class RandomizedSet:
    def __init__(self):
        self.values = []
        self.positions = {}

    def insert(self, value):
        if value in self.positions:
            return False
        self.positions[value] = len(self.values)
        self.values.append(value)
        return True

    def remove(self, value):
        if value not in self.positions:
            return False
        index = self.positions[value]
        last = self.values[-1]
        self.values[index] = last
        self.positions[last] = index
        self.values.pop()
        del self.positions[value]
        return True

    def getRandom(self):
        return random.choice(self.values)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L6 __init__: self.values = []
self=RandomizedSet{'values':[]}

L7 __init__: self.positions = {}
self=RandomizedSet{'values':[], 'positions':{}}

L10 insert: if value in self.positions:
self=RandomizedSet{'values':[], 'positions':{}}; value=1

L12 insert: self.positions[value] = len(self.values)
self=RandomizedSet{'values':[], 'positions':{...:...}}; value=1

L13 insert: self.values.append(value)
self=RandomizedSet{'values':[...], 'positions':{...:...}}; value=1

L10 insert: if value in self.positions:
self=RandomizedSet{'values':[...], 'positions':{...:...}}; value=2

L12 insert: self.positions[value] = len(self.values)
self=RandomizedSet{'values':[...], 'positions':{...:..., ...:...}}; value=2

L13 insert: self.values.append(value)
self=RandomizedSet{'values':[..., ...], 'positions':{...:..., ...:...}}; value=2

... 3 intermediate state changes omitted ...

L23 remove: self.values.pop()
self=RandomizedSet{'values':[...], 'positions':{...:..., ...:...}}; value=1; index=0; last=2

L24 remove: del self.positions[value]
self=RandomizedSet{'values':[...], 'positions':{...:...}}; value=1; index=0; last=2

L28 getRandom: return random.choice(self.values)
self=RandomizedSet{'values':[...], 'positions':{...:...}}

L17 remove: if value not in self.positions:
self=RandomizedSet{'values':[...], 'positions':{...:...}}; value=1

L6 __init__: self.values = []
self=RandomizedSet{'values':[]}

L7 __init__: self.positions = {}
self=RandomizedSet{'values':[], 'positions':{}}

L10 insert: if value in self.positions:
self=RandomizedSet{'values':[], 'positions':{}}; value=7

L12 insert: self.positions[value] = len(self.values)
self=RandomizedSet{'values':[], 'positions':{...:...}}; value=7

L13 insert: self.values.append(value)
self=RandomizedSet{'values':[...], 'positions':{...:...}}; value=7

L10 insert: if value in self.positions:
self=RandomizedSet{'values':[...], 'positions':{...:...}}; value=7

L17 remove: if value not in self.positions:
self=RandomizedSet{'values':[...], 'positions':{...:...}}; value=7

L19 remove: index = self.positions[value]
self=RandomizedSet{'values':[...], 'positions':{...:...}}; value=7; index=0

L20 remove: last = self.values[-1]
self=RandomizedSet{'values':[...], 'positions':{...:...}}; value=7; index=0; last=7

L23 remove: self.values.pop()
self=RandomizedSet{'values':[], 'positions':{...:...}}; value=7; index=0; last=7

L24 remove: del self.positions[value]
self=RandomizedSet{'values':[], 'positions':{}}; value=7; index=0; last=7

Why the solution is correct

Insertion adds one new aligned entry. Swap-delete removes exactly the requested member and repairs the sole other index that may change; removing the final element also works because its temporary mapping is deleted afterward. Every member occupies one list slot, so uniform index selection gives uniform member selection.

Time and space

Expected amortized O(1) per operation using hashing, dynamic-array append/pop and random indexing; O(n) stored entries. Hash/equality costs depend on the value type.

Common mistakes

Forgetting to update the moved value's index corrupts later removals. Sampling dictionary iteration positions requires linear work unless a separate indexable structure is maintained.

Reasoning card

Transfer exercise

Allow duplicates with a value-to-set-of-indices map, and state how sampling should weight repeated occurrences.