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

Insert Delete GetRandom O(1) - Duplicates allowed

Hard ArrayTwo Pointers LeetCode

Design a collection that supports three operations — insert, remove, and getRandom — each running in average O(1) time, with the twist that the same value is allowed to appear in the collection more than once.

insert(val) returns true only for a value not already present; remove(val) returns true if one occurrence was removed. getRandom() is called only when non-empty and samples uniformly among stored occurrences, so duplicate values have proportionally greater probability.

Input Format
Implement the class RandomizedCollection. Fixtures contain constructor arguments and a list of [method, ...arguments] calls. Each fixture starts with a fresh instance.
Output Format
Return the specified result from each method. The displayed output lists results in call order; undefined results appear as null.

Sample Input and Output

Example 1 · Run Sample

Input
constructorArgs = []
operations = [["insert",1],["insert",1],["getRandom"],["remove",1],["getRandom"],["remove",1],["remove",1]]
Output
[true,false,1,true,1,true,false]

Example 2

Input
constructorArgs = []
operations = [["insert",1],["insert",2],["remove",1],["getRandom"],["insert",2],["remove",2],["getRandom"]]
Output
[true,true,true,2,false,true,2]
Constraints
  • -2^31 <= val <= 2^31 - 1
  • At most 2 * 10^5 calls
Test Cases (2)
Case 1
Args: [[],[["insert",1],["insert",1],["getRandom"],["remove",1],["getRandom"],["remove",1],["remove",1]]] Expected: [true,false,1,true,1,true,false]
Case 2
Args: [[],[["insert",1],["insert",2],["remove",1],["getRandom"],["insert",2],["remove",2],["getRandom"]]] Expected: [true,true,true,2,false,true,2]
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.

javascript
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