Hard

Quiz

#381 Insert Delete GetRandom O(1) - Duplicates allowed

APPROACH

Build a multiset data structure that permits duplicate values, supporting insert, remove, and random retrieval each in average O(1) time.

Implement the RandomizedCollection class:

- RandomizedCollection() Constructs an empty collection.

- bool insert(int val) Adds one copy of val (duplicates allowed); returns true if val was not previously present, false if it was.

- bool remove(int val) Removes one copy of val if any exist; returns true if a copy was found and removed, false otherwise.

- int getRandom() Returns a random element with probability proportional to how many times it appears (the collection is guaranteed non-empty when called).

Each function must work on average O(1) time complexity.

Example 1:

Input

["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]

[[], [1], [1], [2], [], [1], []]

Output

[null, true, false, true, 2, true, 1]

Example 2:

Explanation

RandomizedCollection randomizedCollection = new RandomizedCollection();

randomizedCollection.insert(1); // return true since the collection does not contain 1.

// Inserts 1 into the collection.

randomizedCollection.insert(1); // return false since the collection contains 1.

// Inserts another 1 into the collection. Collection now contains [1,1].

randomizedCollection.insert(2); // return true since the collection does not contain 2.

// Inserts 2 into the collection. Collection now contains [1,1,2].

randomizedCollection.getRandom(); // getRandom should:

// - return 1 with probability 2/3, or

// - return 2 with probability 1/3.

randomizedCollection.remove(1); // return true since the collection contains 1.

// Removes 1 from the collection. Collection now contains [1,2].

randomizedCollection.getRandom(); // getRandom should return 1 or 2, both equally likely.

1 of 4

1:00

What is the optimal approach for this problem?