Insert Delete GetRandom O(1)

medium array hash map design

Problem

Implement the RandomizedSet class: RandomizedSet() Initializes the RandomizedSet object. bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise. int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called).

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()];
    }
};

Explanation

We need a set supporting insert, remove, and a uniform getRandom all in O(1). No single data structure gives all three, so we combine two: a dynamic array arr for the values, and a hash map idx mapping each value to its position in that array.

The array makes getRandom trivial — pick a random index. The map makes membership checks and lookups instant, which insert and remove both rely on.

insert(v): if v is already a key in idx we do nothing; otherwise we append v to arr and record idx[v] as its new index.

The clever part is remove(v): deleting from the middle of an array is normally slow, so we use the swap-with-last trick. We move the array's last value into the slot i that v occupied, update that moved value's entry in idx to i, then pop the tail and delete v from the map. The array stays gap-free.

Example: after inserting 1, 2, 3 we have arr = [1, 2, 3], idx = {1:0, 2:1, 3:2}. remove(2) overwrites slot 1 with the last value 3, sets idx[3] = 1, then pops, leaving arr = [1, 3], idx = {1:0, 3:1} — all in constant time.

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