Sponsored
Sponsored
This approach uses a HashMap to store the indices of elements and a List to store the elements themselves. The HashMap enables quick updates for insertions and deletions, while the List ensures that we can select a random element efficiently.
We maintain a Count of all elements using a map, where each element maps to a set of indices in the List. During removal, we swap the element with the last element in the list (if not already last), update the HashMap accordingly, and remove the last entry from the list for O(1) complexity.
Time Complexity: O(1) average for all operations.
Space Complexity: O(n), where n is the number of elements in the multiset.
1class RandomizedCollection {
2 constructor() {
3 this.nums = [];
4 this.indices = new Map();
5 }
6
7 insert(val) {
8 const contained = this.indices.has(val);
9 if (!contained) this.indices.set(val, new Set());
10 this.indices.get(val).add(this.nums.length);
11 this.nums.push(val);
12 return !contained;
13 }
14
15 remove(val) {
16 if (!this.indices.has(val) || this.indices.get(val).size === 0) return false;
17 const removeIndex = [...this.indices.get(val).keys()][0];
18 this.indices.get(val).delete(removeIndex);
19 const lastVal = this.nums[this.nums.length - 1];
20 this.nums[removeIndex] = lastVal;
21 if (this.indices.get(lastVal).has(this.nums.length - 1)) {
22 this.indices.get(lastVal).delete(this.nums.length - 1);
23 this.indices.get(lastVal).add(removeIndex);
24 }
25 this.nums.pop();
26 if (this.indices.get(val).size === 0) this.indices.delete(val);
27 return true;
28 }
29
30 getRandom() {
31 const randomIndex = Math.floor(Math.random() * this.nums.length);
32 return this.nums[randomIndex];
33 }
34}The JavaScript solution uses an array to maintain the elements and a Map to hold sets of indices, ensuring efficient insertion and removal of elements while maintaining average O(1) time complexity for each operation. The random choice is done via Math.random on the length of the array.