Insert Delete GetRandom O(1)

How it works

To achieve O(1) for all operations including getRandom(), we combine a hash map with a dynamic array. The array stores the actual values and allows random access, while the hash map stores each value's index in the array for fast lookups. The tricky part is deletion: removing from the middle of an array is O(n). We solve this by swapping the element to delete with the last element, then removing from the end in O(1) time. This swap-and-pop technique is a common pattern for O(1) deletion from unordered collections.

Steps

1. Initialize a hash map numMap (value to index) and a list nums.
2. insert(val): If val exists in the map, return false. Otherwise, add val to the end of the list and store its index in the map. Return true.
3. remove(val): If val doesn't exist, return false. Get the index of val, swap it with the last element in the list, update the swapped element's index in the map, remove the last element from the list, and delete val from the map. Return true.
4. getRandom(): Return a random element from the list using a random index.

Complexity

• Time complexity: O(1) for each function call.
• Space complexity: O(n)

Things to watch for

Not Updating the Swapped Element's Index

During removal, when swapping the element to delete with the last element, a critical step is updating the last element's index in the hash map before removing anything. Forgetting numMap[last] = idx causes the hash map to have a stale index for the swapped element, leading to incorrect behavior on subsequent operations involving that value.

Edge Case When Removing the Last Element

When the element to remove is already at the last position (i.e., idx == len(nums) - 1), the swap operation effectively swaps the element with itself. While this works correctly in most implementations, some code paths may have issues if they delete from the map before updating it. The order of operations matters: update the map first, then remove from both the list and map.

Using Hash Map Only Without Array

A common initial approach is to use only a hash map, which provides O(1) insert and delete but O(n) for getRandom() since hash maps do not support random index access. Converting keys to a list on each getRandom() call defeats the O(1) requirement. The combination of hash map plus array is essential, where the array enables O(1) random access and the hash map enables O(1) lookup for the swap-and-pop deletion technique.

import random

class RandomizedSet:

    def __init__(self):
        self.numMap = {}
        self.nums = []

    def insert(self, val: int) -> bool:
        if val in self.numMap:
            return False
        self.numMap[val] = len(self.nums)
        self.nums.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.numMap:
            return False
        idx = self.numMap[val]
        last = self.nums[-1]
        self.nums[idx] = last
        self.numMap[last] = idx
        self.nums.pop()
        del self.numMap[val]
        return True

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

class RandomizedSet {
private:
    unordered_map<int, int> numMap;
    vector<int> nums;

public:
    RandomizedSet() {}

    bool insert(int val) {
        if (numMap.count(val)) return false;
        numMap[val] = nums.size();
        nums.push_back(val);
        return true;
    }

    bool remove(int val) {
        if (!numMap.count(val)) return false;
        int idx = numMap[val];
        int last = nums.back();
        nums[idx] = last;
        numMap[last] = idx;
        nums.pop_back();
        numMap.erase(val);
        return true;
    }

    int getRandom() {
        return nums[rand() % nums.size()];
    }
};