Insert Delete GetRandom O(1) LeetCode 380

LeetCode 380 asks you to design a data structure called RandomizedSet that supports three operations: insert(val) which inserts val if not present and returns true, otherwise returns false; remove(val) which removes val if present and returns true, otherwise returns false; and getRandom() which returns a random element from the current set, with each element equally likely to be chosen.

The key constraint is that all three operations must run in average O(1) time. This rules out naive implementations that use only a single data structure. Understanding why each structure alone fails — and how to combine them — is the core insight of this problem.

This is a classic data structure design problem that appears frequently in FAANG interviews. It tests your ability to combine multiple data structures to achieve performance guarantees that no single structure can provide on its own.

A HashMap alone handles insert and remove in O(1), but getRandom breaks down. To pick a random element you need to convert the key set into a list or iterate through it, which takes O(n) time. There is no way to index into a HashMap by position, so you cannot directly pick the kth element.

An array (or list) alone makes getRandom trivial — just pick a random index in O(1). But remove is O(n) because you have to search for the element and then shift all subsequent elements left to fill the gap. Even with a HashSet you can check membership in O(1), but the actual deletion from the underlying array is still O(n).

Neither structure alone satisfies all three requirements. The solution is to use both together: a HashMap for O(1) lookup and deletion bookkeeping, and an array for O(1) random access. A clever swap trick lets you remove from the array in O(1) by eliminating the costly shift.

The classic problem with removing from an array is that you must shift all elements after the removed element one position left — that is O(n). The swap-to-back trick eliminates this entirely by swapping the target element with the last element in the array and then popping the last position.

After the swap, the element that was last is now at the removed element's old index. You must update the HashMap to reflect its new index. Then you pop the last position — a true O(1) operation. The element you wanted to remove is gone, and no shifting occurred.

This trick only works because the set has no notion of order. If the problem required maintaining insertion order or sorted order, swapping would violate that invariant. RandomizedSet only needs uniform random access, so order within the array does not matter at all.

The insert operation is straightforward. First check if val is already in the HashMap — if it is, return false immediately since the set does not allow duplicates. If val is not present, append it to the end of the array and record its index in the HashMap.

Appending to the end of a dynamic array (like Python list or Java ArrayList) is amortized O(1). Recording the index in the HashMap is O(1). So the entire insert operation is O(1) amortized.

The HashMap maps each value to its current index in the array. This mapping is what makes O(1) removal possible — you can jump directly to any element's position without scanning the array.

The remove operation uses the swap-to-back trick. Start by checking if val exists in the HashMap — if not, return false. If it does, retrieve its current index. Swap the element at that index with the last element in the array, then update the HashMap for the swapped element to reflect its new index.

Next, pop the last element of the array (which is now val after the swap) in O(1), and delete val from the HashMap. Return true. Every step is O(1): the HashMap lookup, the array swap, the HashMap update, the array pop, and the HashMap delete.

One subtle edge case: if val happens to be the last element already, then swapping it with itself is a no-op, and you just pop and delete. The logic handles this naturally without any special casing as long as you update the HashMap correctly before or after.

In Python, the implementation uses a list for the array and a dict for the HashMap. The list supports O(1) append and O(1) pop from the end. The dict provides O(1) average lookup and deletion. For getRandom, Python's random.choice(self.vals) picks a uniform random element in O(1) since list indexing is O(1).

In Java, use an ArrayList for the array and a HashMap for the mapping. ArrayList.add() and ArrayList.remove(size-1) are O(1) amortized. For getRandom, use new Random().nextInt(list.size()) to generate a random index and return list.get(index). Both implementations follow the exact same logic — the language choice does not affect the algorithm.

The overall space complexity is O(n) for both the array and the HashMap, where n is the number of elements currently in the set. The time complexity is O(1) average for all three operations due to the amortized O(1) behavior of dynamic array append and the O(1) average performance of hash operations.

Insert Delete GetRandom O(1) belongs to a family of design problems where you must combine multiple data structures to meet strict time complexity requirements. The LRU Cache (LeetCode 146) uses a HashMap plus a doubly linked list to achieve O(1) get and put. The pattern is the same: one structure for O(1) lookup, another for O(1) ordered access.

The LFU Cache (LeetCode 460) adds a frequency layer on top of LRU, requiring three HashMaps and a doubly linked list. The Max Frequency Stack (LeetCode 895) uses a HashMap of stacks grouped by frequency. In all these problems, the key insight is that no single structure can do everything — you need to compose multiple structures and keep them in sync.

Random Pick with Weight (LeetCode 528) extends the random selection idea: instead of uniform random, elements have weights. It uses prefix sums and binary search to pick proportionally. Understanding RandomizedSet's O(1) uniform random access is a prerequisite for tackling the weighted variant and for any problem involving randomized data structure design.