Log inSign up
hardLeetCodeNot Started

Insert Delete GetRandom O(1) - Duplicates Allowed

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

Implement the RandomizedCollection class: - RandomizedCollection(): Initializes the empty RandomizedCollection object. - bool insert(int val): Inserts an item val into the multiset, even if the item is already present. Returns true if the item was not present, false otherwise. - bool remove(int val): Removes an item val from the multiset if present. Returns true if the item is present, false otherwise. Note that if val has multiple occurrences in the multiset, any one occurrence should be removed. - int getRandom(): Returns a random element from the current collection of elements. The probability of each element being returned must be linearly proportional to the count of that element in the multiset.

All operations must run in average O(1) time complexity.

Example 1 · Example 1: Multiple Copies:

Input: insert(1), insert(1), insert(2), getRandom(), remove(1), getRandom()
Output: [true, false, true, 1 or 2 (2/3 vs 1/3), true, 1 or 2 (1/2 each)]
Explanation: - insert(1) returns true (new key).\n- insert(1) returns false (already present).\n- insert(2) returns true.\n- getRandom(): 1 has 2/3 chance, 2 has 1/3 chance.\n- remove(1) removes one copy of 1, returns true.\n- getRandom(): 1 and 2 each have 1/2 chance.

Constraints:

  • -231 <= val <= 231 - 1
  • At most 2 * 105 calls in total will be made to insert, remove, and getRandom.
  • There will be at least one element in the data structure when getRandom is called.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Extend the swap-with-last pattern from sets to multisets.
  • Handle edge cases where the removed element is at the end of the array.
  • Implement the complete multiset random sampler across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Multiset with O(1) random sampling proportional to frequency.
  • O(1) insert and delete with duplicate elements.
  • No sorted order required.

Algorithmic Decision Tree:

  • Array stores raw values for proportional sampling.
  • Hash map stores value -> Set<index>.
  • Swap target index with tail index for O(1) deletion.

Connected Patterns:

Insert Delete GetRandom O(1)Random Pick with BlacklistRandomized Collection

1. Dynamic Array with Linear Removal

Intuition

Keep all elements in a vector. insert checks if present (to return boolean flag) and appends. remove searches for the first occurrence of val, erases it in O(N), and shifts remaining elements. getRandom picks a random index.

When to apply: When total operations are few.

Algorithm

  1. Step 1: In insert(val), check if val in array; append val; return !present.
  2. Step 2: In remove(val), find index of val; if not found return false; else erase at index and return true.
  3. Step 3: In getRandom(), return array[rand() % size].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <cstdlib>
5
6using namespace std;
7
8class RandomizedCollection {
9 vector<int> nums;
10public:
11 RandomizedCollection() {}
12
13 bool insert(int val) {
14 bool present = (find(nums.begin(), nums.end(), val) != nums.end());
15 nums.push_back(val);
16 return !present;
17 }
18
19 bool remove(int val) {
20 auto it = find(nums.begin(), nums.end(), val);
21 if (it == nums.end()) return false;
22 nums.erase(it);
23 return true;
24 }
25
26 int getRandom() {
27 return nums[rand() % nums.size()];
28 }
29};
30
31int main() {
32 RandomizedCollection rc;
33 cout << boolalpha;
34 cout << "insert(1): " << rc.insert(1) << endl; // true
35 cout << "insert(1): " << rc.insert(1) << endl; // false
36 cout << "insert(2): " << rc.insert(2) << endl; // true
37 cout << "getRandom(): " << rc.getRandom() << endl;
38 cout << "remove(1): " << rc.remove(1) << endl; // true
39 cout << "getRandom(): " << rc.getRandom() << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N) insert/remove, O(1) getRandom
  • Space complexity: O(N)

2. Hash Map Frequency Counter

Intuition

Keep countMap: val -> count and total count. Insert increments count, remove decrements count. For getRandom, generate random integer r in [0, total - 1], iterate through unique keys subtracting their count from r until r < 0.

When to apply: When many duplicates exist and getRandom calls are infrequent.

Algorithm

  1. Step 1: In insert(val), increment count in map and increment totalCount. Return true if count was 1.
  2. Step 2: In remove(val), if val not in map return false. Decrement count and totalCount; if 0 erase from map.
  3. Step 3: In getRandom(), pick r in [0, totalCount - 1]. Iterate map entries: r -= count; if r < 0 return key.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_map>
3#include <cstdlib>
4
5using namespace std;
6
7class RandomizedCollection {
8 unordered_map<int, int> counts;
9 int totalCount = 0;
10public:
11 RandomizedCollection() {}
12
13 bool insert(int val) {
14 bool notPresent = (counts[val] == 0);
15 counts[val]++;
16 totalCount++;
17 return notPresent;
18 }
19
20 bool remove(int val) {
21 if (counts.find(val) == counts.end() || counts[val] == 0) return false;
22 counts[val]--;
23 totalCount--;
24 if (counts[val] == 0) counts.erase(val);
25 return true;
26 }
27
28 int getRandom() {
29 int r = rand() % totalCount;
30 for (const auto& [k, v] : counts) {
31 r -= v;
32 if (r < 0) return k;
33 }
34 return counts.begin()->first;
35 }
36};
37
38int main() {
39 RandomizedCollection rc;
40 cout << boolalpha;
41 cout << "insert(1): " << rc.insert(1) << endl;
42 cout << "insert(1): " << rc.insert(1) << endl;
43 cout << "insert(2): " << rc.insert(2) << endl;
44 cout << "getRandom(): " << rc.getRandom() << endl;
45 cout << "remove(1): " << rc.remove(1) << endl;
46 cout << "getRandom(): " << rc.getRandom() << endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(1) insert/remove, O(U) getRandom
  • Space complexity: O(U)

3. Dynamic Array + Hash Map of Index Sets

Intuition

Store raw elements in vector nums. Store indices in map: val -> unordered_set<int>. On insert(val): add index nums.size() to map[val], push to nums. On remove(val): take any index removeIdx from map[val]. Let lastVal = nums.back(). Overwrite nums[removeIdx] = lastVal. Update map[lastVal]: insert removeIdx, erase nums.size() - 1. Erase removeIdx from map[val]. Pop back from nums. If map[val] is empty, delete from map.

When to apply: Standard optimal solution for uniform proportional sampling with duplicates.

Algorithm

  1. Step 1: In insert(val): check if map contains val. Record index nums.size() into map[val]. Push val to nums. Return !present.
  2. Step 2: In remove(val): if map doesn't contain val return false.
  3. Step 3: Extract an index removeIdx from map[val].
  4. Step 4: Get lastVal = nums.back(). Overwrite nums[removeIdx] = lastVal.
  5. Step 5: In map[lastVal], insert removeIdx, and erase nums.size() - 1.
  6. Step 6: Erase removeIdx from map[val]. If map[val] is empty, erase val from map. Pop from nums. Return true.
  7. Step 7: In getRandom(): return nums[rand() % nums.size()].

Interactive Trace for RandomizedCollection

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Two 1s inserted
Visual state
Values and pointers at this exact step
pointers
S
1
1
0
↑ idx 0
1
↑ idx 1
Check / comparison
nums = [1, 1]
Decision / next transition
Two instances tracked at indices 0 and 1.
Why this step matters

Step 1: Two 1s inserted. nums = [1, 1], map[1] = {0, 1}.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <unordered_set>
5#include <cstdlib>
6
7using namespace std;
8
9class RandomizedCollection {
10 vector<int> nums;
11 unordered_map<int, unordered_set<int>> valToIndices;
12public:
13 RandomizedCollection() {}
14
15 bool insert(int val) {
16 bool notPresent = (valToIndices.find(val) == valToIndices.end() || valToIndices[val].empty());
17 valToIndices[val].insert(nums.size());
18 nums.push_back(val);
19 return notPresent;
20 }
21
22 bool remove(int val) {
23 if (valToIndices.find(val) == valToIndices.end() || valToIndices[val].empty()) return false;
24
25 int removeIdx = *(valToIndices[val].begin());
26 valToIndices[val].erase(removeIdx);
27
28 int lastVal = nums.back();
29 int lastIdx = nums.size() - 1;
30
31 if (removeIdx != lastIdx) {
32 nums[removeIdx] = lastVal;
33 valToIndices[lastVal].erase(lastIdx);
34 valToIndices[lastVal].insert(removeIdx);
35 }
36
37 nums.pop_back();
38 if (valToIndices[val].empty()) valToIndices.erase(val);
39 return true;
40 }
41
42 int getRandom() {
43 return nums[rand() % nums.size()];
44 }
45};
46
47int main() {
48 RandomizedCollection rc;
49 cout << boolalpha;
50 cout << "insert(1): " << rc.insert(1) << endl; // true
51 cout << "insert(1): " << rc.insert(1) << endl; // false
52 cout << "insert(2): " << rc.insert(2) << endl; // true
53 cout << "getRandom(): " << rc.getRandom() << endl;
54 cout << "remove(1): " << rc.remove(1) << endl; // true
55 cout << "getRandom(): " << rc.getRandom() << endl;
56 return 0;
57}

Time & Space Complexity

  • Time complexity: O(1) average for all operations
  • Space complexity: O(N)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Dynamic Array with Linear SearchO(1) insert/getRandom, O(N) removeO(N)Append to array on insert. Scan array to find an occurrence on remove and shift remaining elements. Uniform random index for getRandom.Array shifting during deletion.
2.Better — Hash Map of FrequenciesO(1) insert/remove, O(U) getRandom (where U is unique keys)O(U)Track frequencies in a hash map. On getRandom, generate random integer up to total size and scan cumulative frequencies.Cumulative frequency scan during sampling.
3.Optimal — Dynamic Array + Hash Map of Index SetsOptimalO(1) average for all operationsO(N)Map each value to an unordered set of its array indices. Overwrite removed element with last array element, synchronize indices, and pop back.Hash set operations.

Common Pitfalls & Crucial Edge Cases

Using `vector<int>` instead of `unordered_set<int>` in the map

Erasing an index from a vector takes O(k) time, violating strict O(1) removal. Use a hash set for index tracking.

Self-swap corruption

If the element being removed is at the very end of the array, swapping it with itself requires care so the index is removed and not re-added.

Incorrect return boolean for `insert` and `remove`

insert returns true only if the element was NOT present before; remove returns true if the element was present.

Crucial Edge Cases to Validate:

  • Deleting an element when the last element is an identical duplicate — Both the removed element and the element swapped from the end have the same value; index set updates must handle this cleanly.
  • Inserting duplicates — Returns false because the element was already present, but the duplicate is still added.
  • Removing the only instance of an element — The key's set becomes empty and should be removed from the map.
  • Single element in the collection — Handled in O(1).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Contrast this directly with the standard unique-element version to show continuity in problem-solving.
  2. Explain why the probability invariant is naturally satisfied by storing duplicates in the array.
  3. Highlight the importance of using a Hash Set for index storage to maintain O(1) index removal.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.When duplicate values are allowed, how must the Hash Map be modified?

2.Why must getRandom have probability proportional to the number of times an element appears?

3.What must be updated when swapping the deleted element with the last element?

Back to DSA Sheet