NeetCode #127LC-380MediumArrays & Hashing
← Back to All Problems#127 · #380 · Insert Delete GetRandom O(1)(O(1) 时间插入、删除和获取随机元素)
📌 Problem Statement & Constraints
Design a data structure that supports
insert(val), remove(val) and getRandom() in average O(1) time. insert returns whether the value was newly added, remove returns whether the value existed, and getRandom returns a uniformly random existing element. Constraints: -2^31 <= val <= 2^31 - 1; at most 2 * 10^5 calls.💡 Core Algorithmic Approaches
- An array alone gives O(1) random access but O(n) removal; a hash map alone gives O(1) insert/remove but cannot sample uniformly without materialising the keys.
- Combine them: the array stores the values, and the map stores each value's index in the array.
remove(val)swaps the target with the last element, updates the moved element's index, then pops the array -- O(1) overall.getRandompicks a uniform index withrandom.choice, which is O(1).
💻 Benchmark Python3 Implementation
import random
class RandomizedSet:
def __init__(self):
self.arr = [] # the values
self.pos = {} # value -> index in arr
def insert(self, val: int) -> bool:
if val in self.pos:
return False
self.pos[val] = len(self.arr)
self.arr.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.pos:
return False
i = self.pos[val]
last = self.arr[-1]
self.arr[i] = last # move the last element into the hole
self.pos[last] = i
self.arr.pop()
del self.pos[val] # must come after the reassignment
return True
def getRandom(self) -> int:
return random.choice(self.arr)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) average per operation: array append/pop are amortised O(1) and hash operations are O(1) on average.
💾 Space Complexity
O(n) for the array and the index map.
⚠️ Interview Pitfalls & Follow-ups
- Deleting from the map before moving the last element: when the removed value is the last element,
self.pos[last] = iwould recreate the entry you just deleted. Order matters. - Removing from the array with
arr.remove(val): O(n) because of the shift. - Using
setand converting to a list ingetRandom: O(n) per call. - Forgetting to update the moved element's index: the map would point at a stale position, breaking later removals.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.