Problem editorial

Insert Delete GetRandom O(1)

MediumDesign PatternsArrayHash TableMath

Editorial

Core insight

Insert Delete GetRandom O(1) · Design Patterns

Core Insight for Insert Delete GetRandom O(1)

The core insight is to leverage the strengths of two data structures to cover each other's weaknesses:

Dynamic Array (ArrayList/Vector): Excellent for getRandom because elements are stored at contiguous indices $[0, size-1]$ . We can generate a random index in $O(1)$ .
Hash Map: Excellent for insert and remove checks because it can map a value to its location in $O(1)$ .

The difficult part is remove. If we simply remove an element from the middle of the array, we incur an $O(N)$ shift cost. However, since the order of elements in our set does not matter, we can avoid shifting.

The "Swap-and-Pop" Trick: To remove an element at index i in $O(1)$ time:

Take the last element in the array.
Overwrite the element at index i with this last element.
Update the hash map to reflect the new index of the moved element.
Remove the last element (which is now a duplicate) from the array. This is an $O(1)$ operation.

Visual Description: Imagine an array [10, 20, 30, 40] and a map {10:0, 20:1, 30:2, 40:3}. If we want to remove 20 (at index 1), we do not shift 30 and 40. Instead, we take 40 (the last element) and move it to index 1. The array becomes [10, 40, 30, 40]. We update the map so 40 points to index 1. Finally, we truncate the array to remove the trailing 40, resulting in [10, 40, 30].

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 380: Insert Delete GetRandom O(1) Solution & Explanation

Problem Overview

TL;DR: The optimal solution combines a dynamic array (for $O(1)$ random access) with a hash map (for $O(1)$ index lookup), utilizing a "swap-and-pop" technique to perform deletions in constant time.

The "Insert Delete GetRandom O(1)" problem asks us to design a data structure that supports insertion, deletion, and retrieval of a random element. The critical constraint is that all three operations must run in average $O(1)$ time complexity. This requires a hybrid approach, as no single standard data structure (like an Array or a HashSet) efficiently supports all three operations simultaneously.

Brute Force Approach for Insert Delete GetRandom O(1)

A naive approach usually involves choosing a single data structure, which forces a trade-off where at least one operation becomes inefficient.

Using an Array (or ArrayList/Vector):
- insert: $O(1)$ (append to end).
- getRandom: $O(1)$ (access by random index).
- remove: $O(N)$ . To remove a value, we must first search for it ( $O(N)$ ) and then remove it. Removing from an array requires shifting all subsequent elements to fill the gap, taking linear time.
Using a Hash Set (or HashMap):
- insert: $O(1)$ .
- remove: $O(1)$ .
- getRandom: $O(N)$ . Hash sets do not support indexed access. To pick a random element, one would typically have to convert the set to a list or iterate through it to a random point, which takes linear time relative to the number of elements.

Why it fails: The problem explicitly demands $O(1)$ time complexity for all operations. With up to $2 \times 10^5$ calls, an $O(N)$ operation inside the interaction loop will result in a total complexity of $O(N^2)$ in the worst case, leading to a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Design Patterns

We maintain two data structures:

list: A dynamic array storing the actual values.
map: A hash map storing value -> index_in_list.

Insert Strategy:

Check if the value exists in map. If yes, return false.
If no, append the value to the end of list.
Add the entry value -> new_index to map.
Return true.

GetRandom Strategy:

Generate a random integer between 0 and list.size() - 1.
Return the element at that index in list.

Remove Strategy:

Check if the value exists in map. If no, return false.
Retrieve the index of the target value from map.
Identify the last element in list.
Swap: Move the last element into the position of the target element in list.
Update Map: Update the map entry for the moved last element to point to its new index (the index of the element being removed).
Pop: Remove the last element from list.
Delete: Remove the target value from map.
Return true.

Execution Flow

Let's trace the operations: insert(10), insert(20), insert(30), remove(20).

Initialize:
- list = []
- map = {}
insert(10):
- 10 is not in map.
- Append 10 to list: [10].
- Add 10 to map: {10: 0}.
- Return true.
insert(20):
- 20 is not in map.
- Append 20 to list: [10, 20].
- Add 20 to map: {10: 0, 20: 1}.
- Return true.
insert(30):
- 30 is not in map.
- Append 30 to list: [10, 20, 30].
- Add 30 to map: {10: 0, 20: 1, 30: 2}.
- Return true.
remove(20):
- Check map: 20 exists at index 1.
- Target index = 1.
- Last element in list is 30 (at index 2).
- Swap: Overwrite index 1 with 30. list is now [10, 30, 30].
- Update Map: Update 30 in map to index 1. map is {10: 0, 20: 1, 30: 1}.
- Pop: Remove last element from list. list is [10, 30].
- Delete: Remove 20 from map. map is {10: 0, 30: 1}.
- Return true.

Proof of Correctness

The correctness relies on the invariant that map always accurately reflects the index of every element in list, and list contains no gaps.

Insertion: Appending to a dynamic array maintains contiguous indices. The map is updated synchronously.
Randomness: Since list indices are always contiguous from 0 to N-1 (guaranteed by the swap-and-pop removal), generating a random index provides a uniform distribution $1/N$ .
Removal: The swap operation ensures we fill the "hole" left by the removed element with an existing element (the last one). This keeps the array dense (no nulls/gaps), preserving the $O(1)$ random access property. Updating the map ensures subsequent lookups for the moved element remain correct.

Pattern Reuse Notes

The Design pattern involving composite data structures is highly transferable.

LeetCode 146: LRU Cache: Combines a Hash Map (for $O(1)$ access) with a Doubly Linked List (for $O(1)$ ordering updates).
LeetCode 155: Min Stack: Augments a standard stack with an auxiliary stack to track the minimum value in $O(1)$ .
LeetCode 225: Implement Stack using Queues: Uses two queues to simulate LIFO behavior.
LeetCode 232: Implement Queue using Stacks: Uses two stacks to simulate FIFO behavior efficiently.

In all these cases, the key is identifying that a single standard structure is insufficient and combining two to satisfy strict complexity constraints.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 380

cpp

1#include <vector>
2#include <unordered_map>
3#include <cstdlib>
4
5class RandomizedSet {
6private:
7    std::vector<int> nums;
8    std::unordered_map<int, int> valToIndex;
9
10public:
11    RandomizedSet() {
12        // Constructor, no specific initialization needed for containers
13    }
14    
15    bool insert(int val) {
16        if (valToIndex.count(val)) {
17            return false;
18        }
19        // Add to the end of the vector
20        nums.push_back(val);
21        // Record the index in the map
22        valToIndex[val] = nums.size() - 1;
23        return true;
24    }
25    
26    bool remove(int val) {
27        if (!valToIndex.count(val)) {
28            return false;
29        }
30        
31        // Get the index of the element to remove
32        int indexToRemove = valToIndex[val];
33        int lastElement = nums.back();
34        
35        // Move the last element to the place of the element to remove
36        nums[indexToRemove] = lastElement;
37        valToIndex[lastElement] = indexToRemove;
38        
39        // Remove the last element
40        nums.pop_back();
41        valToIndex.erase(val);
42        
43        return true;
44    }
45    
46    int getRandom() {
47        // Generate random index
48        int randomIndex = rand() % nums.size();
49        return nums[randomIndex];
50    }
51};

Java Solution for LeetCode 380

java

1import java.util.*;
2
3class RandomizedSet {
4    private List<Integer> nums;
5    private Map<Integer, Integer> valToIndex;
6    private Random random;
7
8    public RandomizedSet() {
9        nums = new ArrayList<>();
10        valToIndex = new HashMap<>();
11        random = new Random();
12    }
13    
14    public boolean insert(int val) {
15        if (valToIndex.containsKey(val)) {
16            return false;
17        }
18        
19        // Add to map and list
20        valToIndex.put(val, nums.size());
21        nums.add(val);
22        return true;
23    }
24    
25    public boolean remove(int val) {
26        if (!valToIndex.containsKey(val)) {
27            return false;
28        }
29        
30        // Get index of element to remove
31        int indexToRemove = valToIndex.get(val);
32        int lastElement = nums.get(nums.size() - 1);
33        
34        // Swap last element with element to remove
35        nums.set(indexToRemove, lastElement);
36        valToIndex.put(lastElement, indexToRemove); // Update map for the moved element
37        
38        // Remove the last element
39        nums.remove(nums.size() - 1);
40        valToIndex.remove(val);
41        
42        return true;
43    }
44    
45    public int getRandom() {
46        return nums.get(random.nextInt(nums.size()));
47    }
48}

Python Solution for LeetCode 380

python

1import random
2
3class RandomizedSet:
4
5    def __init__(self):
6        self.nums = []
7        self.val_to_index = {}
8
9    def insert(self, val: int) -> bool:
10        if val in self.val_to_index:
11            return False
12        
13        self.nums.append(val)
14        self.val_to_index[val] = len(self.nums) - 1
15        return True
16
17    def remove(self, val: int) -> bool:
18        if val not in self.val_to_index:
19            return False
20        
21        # Get index of element to remove
22        idx_to_remove = self.val_to_index[val]
23        last_val = self.nums[-1]
24        
25        # Move last element to the spot of the element to remove
26        self.nums[idx_to_remove] = last_val
27        self.val_to_index[last_val] = idx_to_remove
28        
29        # Remove the last element
30        self.nums.pop()
31        del self.val_to_index[val]
32        
33        return True
34
35    def getRandom(self) -> int:
36        return random.choice(self.nums)

AI Coach Insight

For Insert Delete GetRandom O(1), focus on explaining why the structure works, not just naming Design Patterns.

Complexity Analysis

Time Complexity: $O(1)$ $O (1)$ Average.
- insert: Hash map insertion is $O(1)$ average. Array append is amortized $O(1)$ .
- remove: Hash map lookup/deletion is $O(1)$ average. Array indexing and pop is $O(1)$ .
- getRandom: Array indexing is $O(1)$ .
Space Complexity: $O(N)$ $O (N)$ .
- We store $N$ elements in the list.
- We store $N$ key-value pairs in the map.

Related Patterns

Pattern: Design Patterns
Subpattern: Design (General/Specific)

This problem falls under the Design pattern because it requires composing two distinct data structures to satisfy specific constraints. It is not about traversing a graph or solving a recurrence relation, but rather about architectural choices in data storage to achieve specific algorithmic bounds.

Common Mistakes & FAQ

Why does my solution get Time Limit Exceeded (TLE)?
- Mistake: Using list.remove(val) or vector::erase with an iterator in the middle of the container.
- Reason: Removing an element from the middle of an array requires shifting all subsequent elements, which is $O(N)$ .
- Consequence: The solution degrades to $O(N)$ for removals, failing large test cases.
Why is getRandom not returning truly random values?
- Mistake: Using a Hash Set and converting it to a list inside getRandom.
- Reason: Converting a set to a list is $O(N)$ . If you try to iterate a set partially, the order depends on hash implementations and isn't strictly "random" in the mathematical sense required, plus iteration is slow.
- Consequence: Efficiency failure ( $O(N)$ complexity) or distribution failure.
Why does remove fail when removing the only element?
- Mistake: Not handling the case where the element to remove is already the last element.
- Reason: If indexToRemove == lastIndex, the swap logic essentially swaps the element with itself.
- Consequence: If the logic deletes from the map before updating the swapped element's index, you might accidentally re-add the deleted key or crash. The reference implementation handles this by updating the map for the lastElement regardless of position, then deleting the val entry.
Why does the map state get corrupted?
- Mistake: Forgetting to update the map entry for the lastElement that was moved.
- Reason: The element that was at the end of the array is now at a new index. The map must reflect this change.
- Consequence: Subsequent remove or insert operations involving that moved element will look up the wrong index, leading to data corruption.

Practise Insert Delete GetRandom O(1) and the problems around it

Insert Delete GetRandom O(1) is a Design Patterns problem, in the Design (General/Specific) subpattern. Once the approach above makes sense, write it yourself and then work through the neighbouring problems that reuse it.

Core insight

Insert Delete GetRandom O(1) · Design Patterns

Core Insight for Insert Delete GetRandom O(1)

The core insight is to leverage the strengths of two data structures to cover each other's weaknesses:

Dynamic Array (ArrayList/Vector): Excellent for getRandom because elements are stored at contiguous indices $[0, size-1]$ . We can generate a random index in $O(1)$ .
Hash Map: Excellent for insert and remove checks because it can map a value to its location in $O(1)$ .

The "Swap-and-Pop" Trick: To remove an element at index i in $O(1)$ time:

Take the last element in the array.
Overwrite the element at index i with this last element.
Update the hash map to reflect the new index of the moved element.
Remove the last element (which is now a duplicate) from the array. This is an $O(1)$ operation.

Deep dive

Full breakdown

Full reasoning, pitfalls, and implementation flow

LeetCode 380: Insert Delete GetRandom O(1) Solution & Explanation

Problem Overview

Brute Force Approach for Insert Delete GetRandom O(1)

A naive approach usually involves choosing a single data structure, which forces a trade-off where at least one operation becomes inefficient.

Using an Array (or ArrayList/Vector):
- insert: $O(1)$ (append to end).
- getRandom: $O(1)$ (access by random index).
- remove: $O(N)$ . To remove a value, we must first search for it ( $O(N)$ ) and then remove it. Removing from an array requires shifting all subsequent elements to fill the gap, taking linear time.
Using a Hash Set (or HashMap):
- insert: $O(1)$ .
- remove: $O(1)$ .
- getRandom: $O(N)$ . Hash sets do not support indexed access. To pick a random element, one would typically have to convert the set to a list or iterate through it to a random point, which takes linear time relative to the number of elements.

Algorithm Strategy: Design Patterns

We maintain two data structures:

list: A dynamic array storing the actual values.
map: A hash map storing value -> index_in_list.

Insert Strategy:

Check if the value exists in map. If yes, return false.
If no, append the value to the end of list.
Add the entry value -> new_index to map.
Return true.

GetRandom Strategy:

Generate a random integer between 0 and list.size() - 1.
Return the element at that index in list.

Remove Strategy:

Check if the value exists in map. If no, return false.
Retrieve the index of the target value from map.
Identify the last element in list.
Swap: Move the last element into the position of the target element in list.
Update Map: Update the map entry for the moved last element to point to its new index (the index of the element being removed).
Pop: Remove the last element from list.
Delete: Remove the target value from map.
Return true.

Execution Flow

Let's trace the operations: insert(10), insert(20), insert(30), remove(20).

Initialize:
- list = []
- map = {}
insert(10):
- 10 is not in map.
- Append 10 to list: [10].
- Add 10 to map: {10: 0}.
- Return true.
insert(20):
- 20 is not in map.
- Append 20 to list: [10, 20].
- Add 20 to map: {10: 0, 20: 1}.
- Return true.
insert(30):
- 30 is not in map.
- Append 30 to list: [10, 20, 30].
- Add 30 to map: {10: 0, 20: 1, 30: 2}.
- Return true.
remove(20):
- Check map: 20 exists at index 1.
- Target index = 1.
- Last element in list is 30 (at index 2).
- Swap: Overwrite index 1 with 30. list is now [10, 30, 30].
- Update Map: Update 30 in map to index 1. map is {10: 0, 20: 1, 30: 1}.
- Pop: Remove last element from list. list is [10, 30].
- Delete: Remove 20 from map. map is {10: 0, 30: 1}.
- Return true.

Proof of Correctness

The correctness relies on the invariant that map always accurately reflects the index of every element in list, and list contains no gaps.

Insertion: Appending to a dynamic array maintains contiguous indices. The map is updated synchronously.
Randomness: Since list indices are always contiguous from 0 to N-1 (guaranteed by the swap-and-pop removal), generating a random index provides a uniform distribution $1/N$ .
Removal: The swap operation ensures we fill the "hole" left by the removed element with an existing element (the last one). This keeps the array dense (no nulls/gaps), preserving the $O(1)$ random access property. Updating the map ensures subsequent lookups for the moved element remain correct.

Pattern Reuse Notes

The Design pattern involving composite data structures is highly transferable.

LeetCode 146: LRU Cache: Combines a Hash Map (for $O(1)$ access) with a Doubly Linked List (for $O(1)$ ordering updates).
LeetCode 155: Min Stack: Augments a standard stack with an auxiliary stack to track the minimum value in $O(1)$ .
LeetCode 225: Implement Stack using Queues: Uses two queues to simulate LIFO behavior.
LeetCode 232: Implement Queue using Stacks: Uses two stacks to simulate FIFO behavior efficiently.

In all these cases, the key is identifying that a single standard structure is insufficient and combining two to satisfy strict complexity constraints.

Feynman coach · Before you peek at the code

Can you explain the core insight in your own words?

If you can explain it before reading code, you’re far more likely to recall it under interview pressure.

Loading your attempt…

Reference Implementation

C++ Solution for LeetCode 380

cpp

1#include <vector>
2#include <unordered_map>
3#include <cstdlib>
4
5class RandomizedSet {
6private:
7    std::vector<int> nums;
8    std::unordered_map<int, int> valToIndex;
9
10public:
11    RandomizedSet() {
12        // Constructor, no specific initialization needed for containers
13    }
14    
15    bool insert(int val) {
16        if (valToIndex.count(val)) {
17            return false;
18        }
19        // Add to the end of the vector
20        nums.push_back(val);
21        // Record the index in the map
22        valToIndex[val] = nums.size() - 1;
23        return true;
24    }
25    
26    bool remove(int val) {
27        if (!valToIndex.count(val)) {
28            return false;
29        }
30        
31        // Get the index of the element to remove
32        int indexToRemove = valToIndex[val];
33        int lastElement = nums.back();
34        
35        // Move the last element to the place of the element to remove
36        nums[indexToRemove] = lastElement;
37        valToIndex[lastElement] = indexToRemove;
38        
39        // Remove the last element
40        nums.pop_back();
41        valToIndex.erase(val);
42        
43        return true;
44    }
45    
46    int getRandom() {
47        // Generate random index
48        int randomIndex = rand() % nums.size();
49        return nums[randomIndex];
50    }
51};

Java Solution for LeetCode 380

java

1import java.util.*;
2
3class RandomizedSet {
4    private List<Integer> nums;
5    private Map<Integer, Integer> valToIndex;
6    private Random random;
7
8    public RandomizedSet() {
9        nums = new ArrayList<>();
10        valToIndex = new HashMap<>();
11        random = new Random();
12    }
13    
14    public boolean insert(int val) {
15        if (valToIndex.containsKey(val)) {
16            return false;
17        }
18        
19        // Add to map and list
20        valToIndex.put(val, nums.size());
21        nums.add(val);
22        return true;
23    }
24    
25    public boolean remove(int val) {
26        if (!valToIndex.containsKey(val)) {
27            return false;
28        }
29        
30        // Get index of element to remove
31        int indexToRemove = valToIndex.get(val);
32        int lastElement = nums.get(nums.size() - 1);
33        
34        // Swap last element with element to remove
35        nums.set(indexToRemove, lastElement);
36        valToIndex.put(lastElement, indexToRemove); // Update map for the moved element
37        
38        // Remove the last element
39        nums.remove(nums.size() - 1);
40        valToIndex.remove(val);
41        
42        return true;
43    }
44    
45    public int getRandom() {
46        return nums.get(random.nextInt(nums.size()));
47    }
48}

Python Solution for LeetCode 380

python

1import random
2
3class RandomizedSet:
4
5    def __init__(self):
6        self.nums = []
7        self.val_to_index = {}
8
9    def insert(self, val: int) -> bool:
10        if val in self.val_to_index:
11            return False
12        
13        self.nums.append(val)
14        self.val_to_index[val] = len(self.nums) - 1
15        return True
16
17    def remove(self, val: int) -> bool:
18        if val not in self.val_to_index:
19            return False
20        
21        # Get index of element to remove
22        idx_to_remove = self.val_to_index[val]
23        last_val = self.nums[-1]
24        
25        # Move last element to the spot of the element to remove
26        self.nums[idx_to_remove] = last_val
27        self.val_to_index[last_val] = idx_to_remove
28        
29        # Remove the last element
30        self.nums.pop()
31        del self.val_to_index[val]
32        
33        return True
34
35    def getRandom(self) -> int:
36        return random.choice(self.nums)

Insert Delete GetRandom O(1)

Core insight

Core Insight for Insert Delete GetRandom O(1)

Full breakdown

LeetCode 380: Insert Delete GetRandom O(1) Solution & Explanation

Problem Overview

Brute Force Approach for Insert Delete GetRandom O(1)

Algorithm Strategy: Design Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 380

Java Solution for LeetCode 380

Python Solution for LeetCode 380

Practise Insert Delete GetRandom O(1) and the problems around it

Related problems

Insert Delete GetRandom O(1)

Core insight

Core Insight for Insert Delete GetRandom O(1)

Full breakdown

LeetCode 380: Insert Delete GetRandom O(1) Solution & Explanation

Problem Overview

Brute Force Approach for Insert Delete GetRandom O(1)

Algorithm Strategy: Design Patterns

Execution Flow

Proof of Correctness

Pattern Reuse Notes

Can you explain the core insight in your own words?

Reference Implementation

C++ Solution for LeetCode 380

Java Solution for LeetCode 380

Python Solution for LeetCode 380

Practise Insert Delete GetRandom O(1) and the problems around it

Related problems