Insert Delete GetRandom O(1) (LeetCode 380)

The problem

Design a RandomizedSet with three operations, each in O(1) average time:

• insert(val): add val if absent; return True if it was added, False if it was already there;
• remove(val): delete val if present; return True if it was removed, False otherwise;
• getRandom(): return a random element, each present element equally likely.

insert(1) -> True
insert(1) -> False   (already present)
remove(2) -> False   (not present)
insert(2) -> True
insert(3) -> True
remove(1) -> True    set is now {2, 3}
getRandom() -> 2 or 3, each with probability 1/2

How to think about it

Start with what each built-in gives you. A Python set (a hash set) does insert and remove in O(1), but it has no O(1) way to pick a random element: you would have to convert it to a list first, which is O(n). A plain list does random.choice in O(1), but finding a value to remove is an O(n) scan, and deleting from the middle shifts every later element.

The key insight: combine the two, and never delete from the middle. Keep the values in an array (for O(1) random picks) and a map from value to its index in that array (for O(1) lookup). To remove a value, look up its index, move the last element into that slot, update the moved element’s index in the map, and pop the last slot. Popping from the end is O(1), and order inside the array doesn’t matter for a set.

Why both structures must stay in sync. Every operation updates the array and the map together. If they ever disagree, remove will overwrite the wrong slot. This is the core habit of the design pattern: map for lookup + array for order or random access, kept consistent on every operation. The tell is “O(1) getRandom” alongside insert and delete.

Approach

1. Keep arr (the values) and idx (value → position in arr).
2. insert(val): if val is in idx, return False. Otherwise record idx[val] = len(arr), append val, return True.
3. remove(val): if val is not in idx, return False. Otherwise:
   • i = idx[val], last = arr[-1];
   • put last at position i and set idx[last] = i;
   • pop the end of arr and delete idx[val]; return True.
4. getRandom(): return random.choice(arr).

Solution

import random

class RandomizedSet:
    def __init__(self): self.idx = {}; self.arr = []
    def insert(self, val):
        if val in self.idx: return False
        self.idx[val] = len(self.arr); self.arr.append(val); return True
    def remove(self, val):
        if val not in self.idx: return False
        i = self.idx[val]; last = self.arr[-1]
        self.arr[i] = last; self.idx[last] = i          # move last element into the hole
        self.arr.pop(); del self.idx[val]; return True  # O(1) pop from the end
    def getRandom(self): return random.choice(self.arr)
# insert(1)->True insert(1)->False remove(2)->False insert(2)->True remove(1)->True

Dry run

The example sequence, tracking both structures:

Removing 1 moved 3 (the last element) into slot 0 and updated idx[3] to 0, then popped the end. getRandom() now picks from [3, 2].

Complexity

• Time: O(1) average per operation. Map lookups and updates are O(1) average, append and pop() from the end are O(1) amortised, and random.choice on a list is O(1).
• Space: O(n). Each value is stored once in the array and once in the map.

Edge cases and pitfalls

• Removing the last element itself. Then last == val and i is the final slot. The code writes it onto itself, then pops it and deletes it from the map, which is correct. Make sure you delete idx[val] after setting idx[last], or this case breaks.
• Wrong order of updates. Popping before reading arr[-1] moves the wrong element.
• getRandom on an empty set is not allowed by the problem; random.choice would raise.
• Using list.remove(val) is O(n) and defeats the purpose.
• Duplicates allowed is LeetCode 381: the map then stores a set of indices per value.

Related problems

• LRU Cache (LeetCode 146): the same “two structures kept in sync” idea, with a linked list for order.
• Design HashMap (LeetCode 706): how the O(1) average map lookup used here actually works.
• LFU Cache (LeetCode 460): a harder design where several maps must stay consistent on every operation.