O(1) Insert Delete and Random Access Set

medium array hash map design

Problem

Design a set that supports three operations in O(1) expected time: insert(v), remove(v), and getRandom() which returns one of the stored values uniformly at random. The trick is to keep the values in a dense array (indexable for getRandom) plus a hash map from value to its array index. To delete, swap the value to the array's tail and pop it — that keeps the array dense and only touches two map entries.

Operationsinsert(1), insert(2), insert(3), remove(2), getRandom()

Afterarr = [1, 3], idx = {1:0, 3:1}

remove(2) overwrites slot 1 with the array's last value 3, then shrinks the array.

operations (e.g. i 1, i 2, i 3, r 2, i 4; i = insert, r = remove)

import random

class RandomizedSet:
    def __init__(self):
        self.arr = []
        self.idx = {}
    def insert(self, v):
        if v in self.idx: return False
        self.idx[v] = len(self.arr)
        self.arr.append(v)
        return True
    def remove(self, v):
        if v not in self.idx: return False
        i = self.idx[v]
        last = self.arr[-1]
        self.arr[i] = last
        self.idx[last] = i
        self.arr.pop()
        del self.idx[v]
        return True
    def getRandom(self):
        return random.choice(self.arr)

class RandomizedSet {
  constructor() { this.arr = []; this.idx = new Map(); }
  insert(v) {
    if (this.idx.has(v)) return false;
    this.idx.set(v, this.arr.length);
    this.arr.push(v);
    return true;
  }
  remove(v) {
    if (!this.idx.has(v)) return false;
    const i = this.idx.get(v), last = this.arr[this.arr.length - 1];
    this.arr[i] = last; this.idx.set(last, i);
    this.arr.pop(); this.idx.delete(v);
    return true;
  }
  getRandom() {
    return this.arr[Math.floor(Math.random() * this.arr.length)];
  }
}

class RandomizedSet {
    List<Integer> arr = new ArrayList<>();
    Map<Integer, Integer> idx = new HashMap<>();
    Random rng = new Random();

    public boolean insert(int v) {
        if (idx.containsKey(v)) return false;
        idx.put(v, arr.size());
        arr.add(v);
        return true;
    }
    public boolean remove(int v) {
        Integer i = idx.get(v);
        if (i == null) return false;
        int last = arr.get(arr.size() - 1);
        arr.set(i, last);
        idx.put(last, i);
        arr.remove(arr.size() - 1);
        idx.remove(v);
        return true;
    }
    public int getRandom() {
        return arr.get(rng.nextInt(arr.size()));
    }
}

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

Time: O(1) per op Space: O(n)