Problem #380: Insert Delete GetRandom O(1)

Intuition & Strategy Breakdown

Combine dynamic array (list) for O(1) random element access with hash map (val -> index) for O(1) insertion and deletion.

Python Solution

class RandomizedSet:
    def __init__(self):
        self.numMap = {}
        self.numList = []

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

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

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

Java Solution

class RandomizedSet {
    private Map map;
    private List list;
    private Random rand;

    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        map.put(val, list.size());
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int idx = map.get(val);
        int lastVal = list.get(list.size() - 1);
        list.set(idx, lastVal);
        map.put(lastVal, idx);
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}