How do you solve Insert Delete GetRandom O(1)?

Use a list to store values and a hash map to store each value's index in the list. For insert, check if the value exists; if not, append it to the list and record its index. For remove, check if the value exists; if so, swap it with the last element in the list, update the map for the swapped element, pop the last element, and delete the removed value from the map. For getRandom, return a random element from the list using O(1) random access. This guarantees average O(1) time for all operations.

What pattern does Insert Delete GetRandom O(1) use?

The Pattern: Hash Maps (Index Mapping with Array) The Heuristic: Combine a hash map for O(1) membership and index tracking with an array for O(1) random access; perform removals by swapping the target element with the last element to maintain O(1) deletion without disrupting array order.

Insert Delete GetRandom O(1) | Hash Maps

Q: What is the time complexity of Insert Delete GetRandom O(1)?

O(1) average. Insert and remove operations perform constant-time hash map lookups and updates, and list append/pop operations are O(1). The swap during removal is a constant-time operation. getRandom uses random.choice on a list, which is O(1).

Problem

Implement a data structure that supports insert, remove, and getRandom operations in average O(1) time.

−2³¹ ≤ val ≤ 2³¹ - 1
At most 2 * 10⁵ calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.

Example

Input: insert(1), insert(2), getRandom(), remove(1), insert(2), getRandom()

Output: [true, true, 1 or 2, true, false, 2]

Initially, the set is empty. insert(1) returns true because 1 was not present. insert(2) returns true because 2 was not present. getRandom() returns either 1 or 2 with equal probability. remove(1) returns true because 1 was present and removed. insert(2) returns false because 2 was already present. getRandom() now returns 2 because it is the only element.

Approach

Straightforward Solution

A naive approach uses a list for storage and a set for membership. Insert and membership checks are O(1) on average, and getRandom is O(1), but removing a value from the middle of the list is O(n) because the list must find and/or shift elements.

Core Observation

The fundamental challenge is to support insert, remove, and getRandom in average O(1) time. Arrays provide O(1) random access, but removing from the middle takes O(n) because elements must shift. Hash maps provide O(1) lookup, insertion, and deletion, but they do not support O(1) random access by index. Combining an array with a value-to-index hash map gives all three operations efficiently.

Path to Optimal

Preview

The key insight is to maintain a list for O(1) random access and a hash map from value to its index in the list. To remove an element in O(1), swap it with the last element in the list, update the hash map accordingly, then pop the last element…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a list to store values and a hash map to store each value's index in the list. For insert, check if the value exists; if not, append it to the list and record its index…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(1) average

Insert and remove operations perform constant-time hash map lookups and updates, and list append/pop operations are O(1). The swap during removal is a constant-time operation. getRandom uses random.choice on a list, which is O(1).

Space

O(n)

The data structure stores all inserted elements in a list and a hash map, both scaling linearly with the number of elements. This space is necessary to maintain O(1) operations.

Solution

Python

1import random
2
3class RandomizedSet:
4
5    def __init__(self):
6        self.values = []
7        self.index = {}
8
9    def insert(self, val: int) -> bool:
10        if val in self.index:
11            return False
12
13        self.index[val] = len(self.values)
14        self.values.append(val)
15        return True
16
17    def remove(self, val: int) -> bool:
18        if val not in self.index:
19            return False
20
21        remove_index = self.index[val]
22        last_value = self.values[-1]
23
24        self.values[remove_index] = last_value
25        self.index[last_value] = remove_index
26
27        self.values.pop()
28        del self.index[val]
29
30        return True
31
32    def getRandom(self) -> int:
33        return random.choice(self.values)

Step-by-Step Solution

1

Initialize List and Hash Map to Track Values and Indices

6self.values = []
7self.index = {}

Objective

To set up the foundational data structures that enable constant-time insertions, removals, and random access.

Key Insight

Using a list allows O(1) random access and efficient appends, while a hash map tracks each value's index in the list for O(1) membership checks and index retrieval. This combination is essential to achieve the required average O(1) time complexity for all operations.

Interview Quick-Check

Core Logic

The list stores the actual values, enabling O(1) random access, while the hash map stores value-to-index mappings for O(1) membership and index lookup.

Common Pitfalls & Bugs

Forgetting to initialize both data structures or mixing their responsibilities can lead to inefficient operations.

2

Insert Values by Appending and Recording Index if Absent

To add a new value to the data structure only if it does not already exist, maintaining O(1) insertion time.

3

Remove Values by Swapping with Last Element and Updating Map

To remove a value in O(1) time by swapping it with the last element and updating the index map accordingly.

4

Return a Random Element Using O(1) List Access

To retrieve a random element from the current set in O(1) time.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 7 Critical lines interviewers watch for.

Line 24 Critical

self.values[remove_index] = last_value

Overwrite the element at remove_index with the last value.

Swapping the target with the last element avoids costly shifting and maintains list integrity for O(1) removal.

Line 25 Critical

self.index[last_value] = remove_index

Update the hash map to reflect the last value's new index.

Maintaining accurate index mappings is critical to prevent inconsistencies and bugs in future operations.

Line 7 Critical

self.index = {}

Initialize an empty hash map to store value-to-index mappings.

The hash map enables O(1) average-time membership checks and index retrieval, which are critical for efficient insert and remove operations.

Full line-by-line criticality + rationale for all 17 lines available on Pro.

Test Your Understanding

Why does swapping the element to remove with the last element in the list enable O(1) removal?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Insert Delete GetRandom O(1) from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Insert Delete GetRandom O(1) drill

or drill a free problem

1	`import random`
2
3	`class RandomizedSet:`
4
5	`def __init__(self):`
6	`self.values = []`
7	`self.index = {}`
8
9	`def insert(self, val: int) -> bool:`
10	`if val in self.index:`
11	`return False`
12
13	`self.index[val] = len(self.values)`
14	`self.values.append(val)`
15	`return True`
16
17	`def remove(self, val: int) -> bool:`
18	`if val not in self.index:`
19	`return False`
20
21	`remove_index = self.index[val]`
22	`last_value = self.values[-1]`
23
24	`self.values[remove_index] = last_value`
25	`self.index[last_value] = remove_index`
26
27	`self.values.pop()`
28	`del self.index[val]`
29
30	`return True`
31
32	`def getRandom(self) -> int:`
33	`return random.choice(self.values)`