• -2³¹ <= val <= 2³¹ - 1
• getRandom is only called when the set has at least one element
• At most 2 × 10⁵ calls will be made across insert, remove, and getRandom

Three requirements, and each one alone points at a different data structure — the trick is that no single structure satisfies all three, so we have to combine two. Let's see why each pulls a different way.

Look at getRandom first. To pick a uniformly random element in O(1), you need your elements packed into consecutive slots 0, 1, 2, … — an array — so you can generate one random index and read that slot instantly. A hash map can't do this: its entries are scattered across buckets with gaps, so there is no clean "pick index between 0 and N-1" move without walking it.

Now look at insert and remove, which must reject duplicates and delete by value. To ask "is val already here?" in O(1) you need a hash map — the very lookup-by-identity you built in Design HashMap. An array can't do that: finding a value in an array means scanning it, O(N).

So the two operations demand opposite structures. The resolution isn't to pick one — it's to keep both, each covering the other's weakness, kept perfectly in sync.

Store the actual elements in an array nums. Alongside it keep a hash map pos that records, for every value, which index of nums it sits at (value → index). Insert appends to the array and records the new index in the map — both O(1). getRandom picks a random index into nums — O(1). The only genuinely hard one is remove, and it has a beautiful fix.

Deleting from the middle of an array is normally O(N), because every element after the hole must slide left to close the gap. But here we don't care about order — it's a set, order is meaningless. That freedom unlocks an O(1) deletion: instead of removing from the middle, swap the doomed element with the last element, then chop off the last slot. The last slot is always free to remove in O(1) (nothing sits after it), and the element that filled the hole just needs its new index recorded in the map.

import random

class RandomizedSet:
    def __init__(self):
        self.nums = []     # the values, packed 0..N-1 for getRandom
        self.pos = {}      # value -> its current index in nums

    def insert(self, val):
        if val in self.pos:        # O(1) duplicate check
            return False
        self.pos[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val):
        if val not in self.pos:
            return False
        idx = self.pos[val]        # where val lives
        last = self.nums[-1]       # the element we'll move into its place
        self.nums[idx] = last      # overwrite the hole with the last element
        self.pos[last] = idx       # tell the map where 'last' moved to
        self.nums.pop()            # drop the now-duplicate final slot (O(1))
        del self.pos[val]          # forget val
        return True

    def getRandom(self):
        return self.nums[random.randrange(len(self.nums))]

Every operation is now O(1) average: the map answers "is it here / where is it" instantly, and the swap-with-last turns middle deletion into end deletion. The cost is O(N) memory for holding each element twice-over (once as a value, once as a map entry) — the same spend memory to buy speed trade from Two Sum, now doubled. The transferable lesson is bigger than this one problem: when two operations demand structures that conflict, keep both and maintain an invariant that links them — here, "pos[v] always equals the current index of v in nums." Every line of both methods exists to preserve that one sentence. And the swap-with-last move is worth memorizing on its own: it is the standard way to delete from an array in O(1) whenever order doesn't matter.