Insert Delete GetRandom O(1) - Duplicates allowed Hard 0 attempts
LeetCode ↗

Insert Delete GetRandom O(1) - Duplicates allowed

Hard ArrayTwo Pointers LeetCode

Implement a data structure that supports insert, remove, and getRandom operations in average O(1) time, allowing duplicates.

Sample Input
["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
Sample Output
[null, true, false, true, 1, true, 1]
Constraints
  • -2^31 <= val <= 2^31 - 1
  • At most 2 * 10^5 calls
Topics
ArrayTwo Pointers

Use an array for O(1) random access and a hash map that maps each value to a set of its indices. To remove in O(1), swap the target with the last element, update index sets, then pop the array.

class RandomizedCollection {
  constructor() {
    this.list = [];
    this.idxMap = new Map();
  }

  insert(val) {
    this.list.push(val);
    if (!this.idxMap.has(val)) this.idxMap.set(val, new Set());
    this.idxMap.get(val).add(this.list.length - 1);
    return this.idxMap.get(val).size === 1;
  }

  remove(val) {
    if (!this.idxMap.has(val) || this.idxMap.get(val).size === 0) return false;
    const removeIdx = this.idxMap.get(val).values().next().value;
    const lastIdx = this.list.length - 1;
    const lastVal = this.list[lastIdx];

    this.list[removeIdx] = lastVal;
    this.idxMap.get(val).delete(removeIdx);
    this.idxMap.get(lastVal).add(removeIdx);
    this.idxMap.get(lastVal).delete(lastIdx);

    this.list.pop();
    if (this.idxMap.get(val).size === 0) this.idxMap.delete(val);
    return true;
  }

  getRandom() {
    return this.list[Math.floor(Math.random() * this.list.length)];
  }
}

Time: O(1) average for insert, remove, and getRandom Space: O(n)

Saved in this browser only. Private to you.

JavaScript