380. Insert Delete GetRandom O(1)
Model: qwen3.5:9b
Topics: Array,Hash Table,Design
FAANG asked: 1
Acceptance rate: 49.1%
Problem Breakdown
We are asked to implement a data structure that behaves like a mathematical set: unique elements only. The core requirement is supporting three operations—insert, remove, and getRandom—all in average O(1) time complexity.
Inputs: An integer value for insertion or removal, plus method calls on the class instance. Outputs: Boolean flags indicating success/failure of insert/remove, and an integer from the set for random retrieval.
Implicit Constraints & Edge Cases:
- Duplicates:
insertmust returnfalseif the element already exists; it should not be added again. Similarly,removereturnsfalseif the element isn’t found. - Randomness: Every valid index in our internal storage must have an equal probability of being picked by
getRandom. This implies we cannot simply pick a random value and search for it (which would require O(N) lookup). We need direct indexing into a list/array. - Removal Cost: Standard array removal is O(N) due to shifting elements. To achieve the follow-up requirement of O(1), we must avoid this shift operation entirely.
Intuition
If I start with just an Array (List): getRandom is easy—just pick a random index—but removing an element requires moving all subsequent items, making it O(N). If I use only a Hash Map: Insert and Remove are fast for lookup, but we lose the ability to do true “random access” without iterating or storing indices.
The brute-force approach (List + HashMap) fails on removal time complexity. To fix this while keeping getRandom at O(1), I need direct indexing into a list and constant-time lookups for existence and position.
Key Insight: The “Swap-Last” technique. When removing an element, instead of shifting elements to fill the gap (which is slow), we swap the target element with the last element in our array. This allows us to pop from the end of the list in O(1). However, this introduces a side effect: the value that was moved into the removed slot now has a new index. We must update our Hash Map entry for that swapped-in value immediately before removing the old one.
Approach
I will maintain two data structures:
- A
List(or dynamic array) to store elements in order, enabling O(1) random access via indexing and amortized O(1) appends/pops at the end. - A Hash Map (
val -> index) mapping each value directly to its current position in the List for O(1) lookup during insert/remove operations.
Algorithm Steps:
insert(val): Check ifvalis already in the map. If not, append it to the list and record its new index (length of list before insertion). Return True. Else return False.remove(val): Look up the index ofval. If found:- Get the last element’s value (
last_val) from the list. - Update the map for
last_val: set its new index to be equal toindex_of_removed_val. - Replace the removed slot with
last_valin the list (conceptually, or just overwrite). - Pop the last element from the list and remove
val’s entry from the map. Return True. Else return False.
- Get the last element’s value (
getRandom(): Generate a random integer between 0 and length of list - 1, then access that index directly in the list.
Complexity Analysis
- Time:
- Insert: O(1) amortized (hash map insert + append).
- Remove: O(1) average (map lookup + swap/pop operations are constant time).
- GetRandom: O(1) direct indexing.
- Space: O(N), where N is the number of elements stored, as we store each element twice (once in list, once in map keys/values).
Solution
import random
class RandomizedSet:
def __init__(self):
# List for storage and indexing.
self.elements = []
# Map to track index of each value for O(1) lookup/swap logic.
self.val_to_index = {}
def insert(self, val: int) -> bool:
if val in self.val_to_index:
return False
self.elements.append(val)
self.val_to_index[val] = len(self.elements) - 1
return True
def remove(self, val: int) -> bool:
# If value doesn't exist, nothing to do.
if val not in self.val_to_index:
return False
index_of_val = self.val_to_index[val]
last_element = self.elements[-1]
n_elements = len(self.elements) - 1
# Move the last element into the position of the removed value.
self.elements[index_of_val] = last_element
# Update the map for the moved element to reflect its new index.
self.val_to_index[last_element] = index_of_val
# Remove from list and remove key from map.
del self.val_to_index[val]
self.elements.pop()
return True
def getRandom(self) -> int:
idx = random.randint(0, len(self.elements) - 1)
return self.elements[idx]
Edge Cases Handled
- Duplicate Insertion: The
insertmethod checks the map first. If present, it returnsFalsewithout modifying state or list size. - Non-existent Removal: The
removemethod checks existence before attempting swap/pop logic to avoid KeyError and ensures correct return value (False). - Map Consistency during Swap: When swapping a removed element with the last one, we explicitly update the map entry for the last element’s new index. This prevents future lookups or removals of that swapped-in element from failing due to stale indices.
- Empty Set on GetRandom: The problem constraints guarantee at least one element exists when
getRandomis called, so no bounds check (like checking if list is empty) is strictly necessary for correctness per spec, though the code relies on valid range passed by constraint.