Log inSign up
hardLeetCodeNot Started

Randomized Collection

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

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

RandomizedCollection is a data structure that contains a collection of numbers, possibly containing duplicates (a multiset), and supports the following operations in average O(1) time:

1. bool insert(int val): Inserts an item val into the collection. Returns true if the collection did not already contain the item, and false otherwise. 2. bool remove(int val): Removes an item val from the collection if present. Returns true if the collection contained the item, and false otherwise. If val has multiple occurrences, removes any single occurrence. 3. int getRandom(): Returns a random element from current collection of elements. The probability of each element being returned is linear to the count of the element in the collection.

You must implement the functions of the class such that each function works with an average time complexity of O(1).

Example 1 · Example 1:

Input: ["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"] [[], [1], [1], [2], [], [1], []]
Output: [null, true, false, true, 2, true, 1]
Explanation: RandomizedCollection randomizedCollection = new RandomizedCollection(); randomizedCollection.insert(1); // return true since collection does not contain 1. Collection = [1] randomizedCollection.insert(1); // return false since collection contains 1. Collection = [1, 1] randomizedCollection.insert(2); // return true since collection does not contain 2. Collection = [1, 1, 2] randomizedCollection.getRandom(); // returns 1 (probability 2/3) or 2 (probability 1/3) randomizedCollection.remove(1); // return true since collection contains 1. Collection = [1, 2] randomizedCollection.getRandom(); // returns 1 or 2 with equal probability 1/2

Constraints:

  • -231 <= val <= 231 - 1
  • At most 2 * 105 calls 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:

  • Master the 3 distinct approaches for Randomized Collection.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

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

Signals to Look For:

  • Randomized Collection
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Prototyping or when total operations are very small.
  • BETTER: When duplicate frequencies are small.
  • OPTIMAL: Whenever O(1) randomized multi-set operations are needed.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Dynamic Array with Linear Scan

Intuition

Use an array/list of integers: - insert(val): Check if val exists in O(n) time and append it to the end in O(1). - remove(val): Search for the first occurrence of val in O(n) time, then shift subsequent elements or swap with the last element to remove in O(n) or O(1). - getRandom(): Select a random index 0 <= idx < size in O(1). While simple, the linear scan causes operations to take O(n) time worst case.

When to apply: Prototyping or when total operations are very small.

Algorithm

  1. Step 1: Maintain a single dynamic array list.
  2. Step 2: On insert(val), scan to check whether val was already present, then append val.
  3. Step 3: On remove(val), scan for the first occurrence of val. If found, remove it and return true; else return false.
  4. Step 4: On getRandom(), pick a random index between 0 and list.size() - 1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cstdlib>
4#include <algorithm>
5
6class RandomizedCollectionBrute {
7 std::vector<int> nums;
8public:
9 RandomizedCollectionBrute() {}
10
11 bool insert(int val) {
12 bool notPresent = (std::find(nums.begin(), nums.end(), val) == nums.end());
13 nums.push_back(val);
14 return notPresent;
15 }
16
17 bool remove(int val) {
18 auto it = std::find(nums.begin(), nums.end(), val);
19 if (it == nums.end()) return false;
20 nums.erase(it);
21 return true;
22 }
23
24 int getRandom() {
25 return nums[rand() % nums.size()];
26 }
27};
28
29int main() {
30 RandomizedCollectionBrute rc;
31 std::cout << (rc.insert(1) ? "true" : "false") << std::endl;
32 std::cout << (rc.insert(1) ? "true" : "false") << std::endl;
33 std::cout << (rc.insert(2) ? "true" : "false") << std::endl;
34 std::cout << rc.getRandom() << std::endl;
35 std::cout << (rc.remove(1) ? "true" : "false") << std::endl;
36 std::cout << rc.getRandom() << std::endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(n) for insert and remove, O(1) for getRandom
  • Space complexity: O(n) for storing items

2. Hash Map of Value to List of Indices

Intuition

To accelerate searches, map each val to a dynamic list of indices where val resides in nums. - insert(val): Append index nums.size() to the list for val in O(1). - remove(val): Take the last index from the list of val. Swap with the last item in nums. However, updating the moved item's index in its list takes O(k) linear time if looking up where that index was stored in its list. By maintaining a list instead of a set/hashset, remove operations take O(k) where k is the duplicate frequency.

When to apply: When duplicate frequencies are small.

Algorithm

  1. Step 1: Maintain nums array and a map from val to a list of integer indices.
  2. Step 2: On insert, check if map contains val, append to nums, and record index in map[val].
  3. Step 3: On remove, retrieve an index of val, swap nums[idx] with the last element of nums, update index records, and pop.
  4. Step 4: On getRandom, return nums[rand() % nums.length].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <cstdlib>
5
6class RandomizedCollectionBetter {
7 std::vector<int> nums;
8 std::unordered_map<int, std::vector<int>> valToIndices;
9public:
10 RandomizedCollectionBetter() {}
11
12 bool insert(int val) {
13 bool notPresent = valToIndices[val].empty();
14 valToIndices[val].push_back(nums.size());
15 nums.push_back(val);
16 return notPresent;
17 }
18
19 bool remove(int val) {
20 if (valToIndices[val].empty()) return false;
21 int removeIdx = valToIndices[val].back();
22 valToIndices[val].pop_back();
23
24 int lastVal = nums.back();
25 int lastIdx = nums.size() - 1;
26
27 if (removeIdx != lastIdx) {
28 nums[removeIdx] = lastVal;
29 // update index in lastVal's list
30 for (int& i : valToIndices[lastVal]) {
31 if (i == lastIdx) {
32 i = removeIdx;
33 break;
34 }
35 }
36 }
37 nums.pop_back();
38 if (valToIndices[val].empty()) {
39 valToIndices.erase(val);
40 }
41 return true;
42 }
43
44 int getRandom() {
45 return nums[rand() % nums.size()];
46 }
47};
48
49int main() {
50 RandomizedCollectionBetter rc;
51 std::cout << (rc.insert(1) ? "true" : "false") << std::endl;
52 std::cout << (rc.insert(1) ? "true" : "false") << std::endl;
53 std::cout << (rc.insert(2) ? "true" : "false") << std::endl;
54 std::cout << rc.getRandom() << std::endl;
55 std::cout << (rc.remove(1) ? "true" : "false") << std::endl;
56 std::cout << rc.getRandom() << std::endl;
57 return 0;
58}

Time & Space Complexity

  • Time complexity: O(1) insert and getRandom, O(k) remove where k is count of duplicate instances
  • Space complexity: O(n) for nums array and index lists

3. Hash Map of Value to Hash Set of Indices + Array Swap

Intuition

To achieve strict average O(1) time for remove: 1. Use nums array to store elements contiguously so getRandom() chooses with exact linear probability proportional to duplicate frequency. 2. Use valToIndices map where each val maps to a hash set of indices. 3. On insert(val): - Check if set for val is empty. - Insert nums.size() into valToIndices[val]. - Append val to nums. Average O(1). 4. On remove(val): - Pick any index removeIdx from valToIndices[val] (e.g. *valToIndices[val].begin()). - Remove removeIdx from valToIndices[val]. - Swap nums[removeIdx] with lastVal = nums.back(): - If removeIdx != lastIdx, replace lastIdx with removeIdx in valToIndices[lastVal] by erasing lastIdx and inserting removeIdx. - Set nums[removeIdx] = lastVal. - Pop the last element from nums. Average O(1). 5. On getRandom(): - Choose a uniformly random integer in [0, nums.size() - 1]. Return nums[idx]. Exact O(1).

When to apply: Whenever O(1) randomized multi-set operations are needed.

Algorithm

  1. Step 1: Initialize dynamic array nums and hash map valToIndices mapping val to a Set of indices.
  2. Step 2: On insert(val), check if val was present, add index nums.length to val's set, push val to nums.
  3. Step 3: On remove(val), return false if val is not in map or its set is empty.
  4. Step 4: Extract an arbitrary index removeIdx from val's set. Retrieve lastVal and lastIdx from nums.
  5. Step 5: If removeIdx != lastIdx, overwrite nums[removeIdx] with lastVal, erase lastIdx and insert removeIdx into lastVal's set.
  6. Step 6: Pop last element from nums and clean up empty key from map.
  7. Step 7: On getRandom(), pick random index between 0 and nums.length - 1 and return nums[index].

Interactive trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
insert(1): 1 is not present
Visual state
Values and pointers at this exact step
pointers
S
1
0
Check / comparison
valToIndices[1] was empty
Decision / next transition
nums = [1], valToIndices = {1: {0}}
Why this step matters

insert(1): 1 is not present. Append to nums at index 0. valToIndices[1] = {0}. Returns true.

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

Time & Space Complexity

  • Time complexity: Average O(1) for insert, remove, and getRandom
  • Space complexity: O(n) auxiliary space for nums array and index sets

Approach Comparison Matrix

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

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Dynamic Array with Linear ScanO(n) for insert and remove, O(1) for getRandomO(n) for storing itemsStore items in a dynamic array. Find and remove targets using linear scan, while getRandom chooses a random index.O(n) for insert and remove, O(1) for getRandom
2.Hash Map of Value to List of IndicesO(1) insert and getRandom, O(k) remove where k is count of duplicate instancesO(n) for nums array and index listsMap each value to an array/list of its indices in the nums vector.O(1) insert and getRandom, O(k) remove where k is count of duplicate instances
3.Hash Map of Value to Hash Set of Indices + Array SwapOptimalAverage O(1) for insert, remove, and getRandomO(n) auxiliary space for nums array and index setsMap each value to an unordered set of its indices. Swap target with last element to achieve true average O(1) across all operations.Average O(1) for insert, remove, and getRandom

Common Pitfalls & Crucial Edge Cases

Using `vector<int>` for index storage

Removing an index from a vector takes O(k) time. An unordered_set<int> allows O(1) index removal.

Order of index updates during swap

If idxToRemove == lastIdx, updating lastVal's set before erasing idxToRemove can cause corruption.

Non-uniform random selection

Must pick uniformly from 0 to array.length - 1.

Crucial Edge Cases to Validate:

  • Removing an element when its instance is at the very end of the array — The element swapped from the end is the element being deleted; must update indices without re-inserting.
  • Multiple identical elements in the array — Random selection selects each with probability proportional to frequency.
  • Removing the last remaining instance of a key — Key's set becomes empty and is erased from the map.
  • Single element collection — All operations run in O(1).

Interview Tips & Best Practices

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

  1. Demonstrate why duplicate tracking requires mapping values to index sets rather than a single index integer.
  2. Walk through the swap-and-pop logic with duplicate values step by step.
  3. Highlight amortized O(1) time complexity across insert, remove, and getRandom.

Quick Comprehension Check

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

1.What data structure combination implements RandomizedCollection (duplicates allowed) in O(1) average time?

2.Why must the map store a Set of indices rather than a simple count?

3.What is the return value of remove(val)?

Back to DSA Sheet