Insert Delete GetRandom O(1) [Medium] — Array + HashMap Design

Problem Statement

Implement RandomizedSet:

insert(val): Insert if not present. Return true if inserted.
remove(val): Remove if present. Return true if removed.
getRandom(): Return a random element uniformly.

All operations O(1) average.

Intuition

Array provides O(1) random access (for getRandom). HashMap provides O(1) lookup. On remove: swap target with last element, update map, pop last.

Solutions

Python

import random

class RandomizedSet:
    def __init__(self):
        self.arr = []
        self.idx = {}  # val → index in arr

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

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

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

Java

class RandomizedSet {
    List<Integer> arr=new ArrayList<>();
    Map<Integer,Integer> idx=new HashMap<>();
    Random rand=new Random();
    public boolean insert(int val){
        if(idx.containsKey(val))return false;
        arr.add(val); idx.put(val,arr.size()-1); return true;
    }
    public boolean remove(int val){
        if(!idx.containsKey(val))return false;
        int last=arr.get(arr.size()-1), i=idx.get(val);
        arr.set(i,last); idx.put(last,i);
        arr.remove(arr.size()-1); idx.remove(val); return true;
    }
    public int getRandom(){return arr.get(rand.nextInt(arr.size()));}
}

C++

class RandomizedSet {
    vector<int> arr; unordered_map<int,int> idx;
public:
    bool insert(int val){
        if(idx.count(val)) return false;
        arr.push_back(val); idx[val]=arr.size()-1; return true;
    }
    bool remove(int val){
        if(!idx.count(val)) return false;
        int last=arr.back(), i=idx[val];
        arr[i]=last; idx[last]=i;
        arr.pop_back(); idx.erase(val); return true;
    }
    int getRandom(){return arr[rand()%arr.size()];}
};

Complexity

insert/remove/getRandom: O(1) average
Space: O(n)