Log inSign up
mediumLeetCodeNot Started

Insert Delete GetRandom O(1)

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

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

Implement the RandomizedSet class: - RandomizedSet(): Initializes the RandomizedSet object. - bool insert(int val): Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise. - bool remove(int val): Removes an item val from the set if present. Returns true if the item was present, false otherwise. - int getRandom(): Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

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

Example 1 · Example 1: Standard Lifecycle:

Input: insert(1), remove(2), insert(2), getRandom(), remove(1), insert(2), getRandom()
Output: [true, false, true, 2, true, false, 2]
Explanation: - insert(1) -> true\n- remove(2) -> false (not present)\n- insert(2) -> true\n- getRandom() -> 1 or 2 equally\n- remove(1) -> true\n- insert(2) -> false (already present)\n- getRandom() -> 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:

  • Combine array and hash map to exploit the strengths of both.
  • Master the swap-with-last idiom for O(1) unordered deletions in dynamic arrays.
  • Implement the complete RandomizedSet 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:

  • Need truly uniform O(1) random sampling from a dynamic collection.
  • Add and remove in O(1) time.
  • No duplicate values.

Algorithmic Decision Tree:

  • Use dynamic array for uniform random indexing.
  • Use hash map for O(1) index tracking.
  • Use swap-with-tail for O(1) deletion.

Connected Patterns:

Insert Delete GetRandom O(1) - Duplicates AllowedRandom Pick with WeightDesign Undergound System

1. Dynamic Array with Linear Search

Intuition

Keep elements in a resizable array. insert checks if the value is present in O(N). remove finds the index in O(N) and shifts remaining elements left in O(N). getRandom picks an index in O(1).

When to apply: When elements are few (N <= 100).

Algorithm

  1. Step 1: In insert(val), iterate through array; if found return false; else append and return true.
  2. Step 2: In remove(val), find index; if not found return false; else erase element and shift remaining elements.
  3. Step 3: In getRandom(), pick random index between 0 and size - 1 and return array[idx].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <cstdlib>
5
6using namespace std;
7
8class RandomizedSet {
9 vector<int> nums;
10public:
11 RandomizedSet() {}
12
13 bool insert(int val) {
14 if (find(nums.begin(), nums.end(), val) != nums.end()) return false;
15 nums.push_back(val);
16 return true;
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 int idx = rand() % nums.size();
28 return nums[idx];
29 }
30};
31
32int main() {
33 RandomizedSet rSet;
34 cout << boolalpha;
35 cout << "insert(1): " << rSet.insert(1) << endl; // true
36 cout << "remove(2): " << rSet.remove(2) << endl; // false
37 cout << "insert(2): " << rSet.insert(2) << endl; // true
38 cout << "getRandom(): " << rSet.getRandom() << endl; // 1 or 2
39 cout << "remove(1): " << rSet.remove(1) << endl; // true
40 cout << "getRandom(): " << rSet.getRandom() << endl; // 2
41 return 0;
42}

Time & Space Complexity

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

2. Hash Set with Linear Random Traversal

Intuition

A hash set provides O(1) membership checks, inserts, and deletes. However, picking a random element requires converting to an array or advancing an iterator by a random offset in O(N) time.

When to apply: When insert and delete are frequent but getRandom is infrequent.

Algorithm

  1. Step 1: In insert(val), if set contains val return false; else add val and return true.
  2. Step 2: In remove(val), if set does not contain val return false; else remove val and return true.
  3. Step 3: In getRandom(), choose random offset k in [0, size - 1], advance iterator k steps, and return element.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_set>
3#include <cstdlib>
4
5using namespace std;
6
7class RandomizedSet {
8 unordered_set<int> set;
9public:
10 RandomizedSet() {}
11
12 bool insert(int val) {
13 if (set.count(val)) return false;
14 set.insert(val);
15 return true;
16 }
17
18 bool remove(int val) {
19 if (!set.count(val)) return false;
20 set.erase(val);
21 return true;
22 }
23
24 int getRandom() {
25 int k = rand() % set.size();
26 auto it = set.begin();
27 advance(it, k);
28 return *it;
29 }
30};
31
32int main() {
33 RandomizedSet rSet;
34 cout << boolalpha;
35 cout << "insert(1): " << rSet.insert(1) << endl;
36 cout << "remove(2): " << rSet.remove(2) << endl;
37 cout << "insert(2): " << rSet.insert(2) << endl;
38 cout << "getRandom(): " << rSet.getRandom() << endl;
39 cout << "remove(1): " << rSet.remove(1) << endl;
40 cout << "getRandom(): " << rSet.getRandom() << endl;
41 return 0;
42}

Time & Space Complexity

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

3. Dynamic Array + Hash Map (Swap with Last)

Intuition

Store elements in a contiguous vector nums and their array positions in a hash map valToIndex. For insert: append to nums and record index in map. For getRandom: pick random index in [0, nums.size() - 1]. For remove: fetch the index of val, swap the last element of nums into that index, update the last element's index in the map, pop from nums, and erase val from the map.

When to apply: Standard optimal solution for uniform random sampling from a dynamic set.

Algorithm

  1. Step 1: In insert(val): check if map contains val; if yes return false. Else, push val to nums, record valToIndex[val] = nums.size() - 1, return true.
  2. Step 2: In remove(val): if map does not contain val return false. Get idx = valToIndex[val].
  3. Step 3: Move lastVal = nums.back() to nums[idx]. Update valToIndex[lastVal] = idx.
  4. Step 4: Pop back from nums, erase val from valToIndex, return true.
  5. Step 5: In getRandom(): return nums[rand() % nums.size()].

Interactive Trace for RandomizedSet

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: After inserting 10 and 20, array is [10, 20] and map has {10: 0, 20: 1}
Visual state
Values and pointers at this exact step
pointers
S
10
20
0
↑ idx 0
1
↑ last
Check / comparison
nums = [10, 20]
Decision / next transition
10 is at index 0, 20 is at index 1.
Why this step matters

Step 1: After inserting 10 and 20, array is [10, 20] and map has {10: 0, 20: 1}.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <cstdlib>
5
6using namespace std;
7
8class RandomizedSet {
9 vector<int> nums;
10 unordered_map<int, int> valToIndex;
11public:
12 RandomizedSet() {}
13
14 bool insert(int val) {
15 if (valToIndex.count(val)) return false;
16 valToIndex[val] = nums.size();
17 nums.push_back(val);
18 return true;
19 }
20
21 bool remove(int val) {
22 if (!valToIndex.count(val)) return false;
23 int idx = valToIndex[val];
24 int lastVal = nums.back();
25
26 nums[idx] = lastVal;
27 valToIndex[lastVal] = idx;
28
29 nums.pop_back();
30 valToIndex.erase(val);
31 return true;
32 }
33
34 int getRandom() {
35 return nums[rand() % nums.size()];
36 }
37};
38
39int main() {
40 RandomizedSet rSet;
41 cout << boolalpha;
42 cout << "insert(1): " << rSet.insert(1) << endl; // true
43 cout << "remove(2): " << rSet.remove(2) << endl; // false
44 cout << "insert(2): " << rSet.insert(2) << endl; // true
45 cout << "getRandom(): " << rSet.getRandom() << endl; // 1 or 2
46 cout << "remove(1): " << rSet.remove(1) << endl; // true
47 cout << "getRandom(): " << rSet.getRandom() << endl; // 2
48 return 0;
49}

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 OnlyO(1) insert/getRandom, O(N) removeO(N)Store elements in a list. insert checks duplicates in O(N). remove searches and shifts elements in O(N). getRandom generates random index in O(1).Linear scan and array shifting.
2.Better — Hash Set OnlyO(1) insert/remove, O(N) getRandomO(N)Store values in a hash set. insert and remove are O(1). getRandom converts set to list or steps an iterator k times.Iterating through hash set to pick random element.
3.Optimal — Dynamic Array + Hash Map (Swap with End)OptimalO(1) average for all operationsO(N)Keep values in vector nums and value-to-index in map. For removal: swap target value with last element, update map, and pop last element.Hash map lookup.

Common Pitfalls & Crucial Edge Cases

Order of operations when target IS the last element

Updating the map index for lastVal before checking if val == lastVal can accidentally re-insert the deleted value.

Using array `splice(index, 1)` in JavaScript

Array splice takes O(N) time because it shifts subsequent elements. You must swap with array[array.length - 1] and use pop().

Non-uniform random generation

Using rand() % N in C++ gives uniform distribution over existing elements.

Crucial Edge Cases to Validate:

  • Deleting the element that is ALREADY the last element in the array — Must not overwrite indices incorrectly when the target element is the last element.
  • Removing an element not present in the set — Returns false immediately.
  • Inserting an already present element — Returns false without duplicating entries.
  • Only one element in the data structure — Array size is 1, getRandom returns that element.

Interview Tips & Best Practices

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

  1. Explain the tension: arrays provide O(1) random access via index, but O(N) search and delete; hash tables provide O(1) search and delete, but no O(1) random index.
  2. Combine them: Dynamic Array (stores values) + Hash Map (stores val -> index in array).
  3. Walk through the swap-with-last deletion step-by-step with a 3-element example.

Quick Comprehension Check

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

1.Why cannot a Hash Map alone support getRandom in O(1) time?

2.How does the swap-with-last trick achieve O(1) deletion from a dynamic array?

3.What is the time complexity of all three operations (insert, remove, getRandom)?

Back to DSA Sheet