Insert Delete GetRandom O(1): Array + HashMap Combo

LeetCode 380 asks you to design a RandomizedSet class that supports three operations, all in average O(1) time:

• insert(val) - inserts val if not already present, returns true if the item was inserted.
• remove(val) - removes val if present, returns true if the item was removed.
• getRandom() - returns a random element from the current set, where each element has an equal probability of being returned.

The challenge is that no single standard data structure gives you O(1) for all three. A hash set handles insert and delete in O(1), but it cannot return a uniformly random element without converting to a list first. An array supports random access, but removing an arbitrary element takes O(n) because of shifting. You need both working together.

The key insight

Use two data structures in tandem: a dynamic array that stores the values, and a hash map that maps each value to its index in the array.

The array gives you getRandom for free - just pick a random index. The hash map gives you O(1) lookup for insert and remove. The only tricky part is removal: you cannot leave a hole in the array, because that would break the uniform random property. The fix is to swap the element you want to remove with the last element, then pop from the end. Popping the last element of an array is O(1), and the swap keeps the array contiguous.

Array (values)HashMap (val to idx)

The approach

1. Insert: Check if val is already in the map. If yes, return false. Otherwise, append val to the array and record map[val] = len(arr) - 1.
2. Remove: Check if val is in the map. If not, return false. Otherwise, look up its index i. Swap arr[i] with the last element arr[-1]. Update the map entry for the swapped element to point to index i. Pop the last element from the array. Delete val from the map.
3. GetRandom: Return arr[random index]. Since the array has no gaps, every element is equally likely.

The code

import random

class RandomizedSet:
    def __init__(self):
        self.arr = []
        self.map = {}

    def insert(self, val):
        if val in self.map:
            return False
        self.map[val] = len(self.arr)
        self.arr.append(val)
        return True

    def remove(self, val):
        if val not in self.map:
            return False
        idx = self.map[val]
        last = self.arr[-1]
        self.arr[idx] = last
        self.map[last] = idx
        self.arr.pop()
        del self.map[val]
        return True

    def getRandom(self):
        return random.choice(self.arr)

A few details worth noting:

• The remove method works correctly even when the element to remove is already the last element. In that case, the "swap" overwrites the last element with itself, updates its map entry to its own index (no-op), then pops it and deletes it from the map.
• random.choice(self.arr) picks a uniformly random index under the hood, which is O(1).
• The hash map uses O(n) space, but that is necessary to achieve O(1) lookup by value.

Complexity

Insert is O(1) amortized because arr.append() occasionally triggers a resize, but that cost is spread over all appends. Remove and getRandom are strict O(1). The space is O(n) for both the array and the hash map.

Building blocks

The core technique here is "swap the target with the last element, then pop." This pattern appears whenever you need O(1) removal from an unordered collection backed by an array. The hash map serves as an index so you can find the target in O(1) instead of scanning.

This same idea of combining two data structures to cover each other's weaknesses shows up in LRU Cache, where a doubly linked list and a hash map work together to achieve O(1) get and put. The linked list handles ordering, the map handles lookup - neither can do both alone.

The hash map for O(1) value lookup is the same building block behind Two Sum, where you store complements as you scan. In both problems, the map converts a linear scan into constant-time access.

Edge cases

• Removing the last element. When val happens to be the last element of the array, the swap is a self-swap. The code still works because it overwrites arr[idx] with last (which equals arr[idx]), updates map[last] = idx (same value), then pops and deletes. No special case needed.
• Duplicate inserts. If val is already present, insert returns false and does nothing. The map check catches this in O(1).
• Single element. With one element, remove sets idx = 0, last = arr[0], swaps with itself, pops, and deletes. getRandom on a single-element array always returns that element.
• Insert after remove. After removing a value, inserting it again works normally because the map entry was fully deleted.

From understanding to recall

Picture two parallel structures: a flat array of values on top, and a dictionary of value-to-index mappings below. Insert appends to the right edge of the array and adds a map entry. Remove swaps the target to the end and chops it off. getRandom picks a random slot from the contiguous array.

The mental image to hold is the "swap to end, then pop" move during removal. That one trick is what makes O(1) deletion possible in an array. Without it, you would need to shift elements left, which costs O(n). The hash map exists purely to find where the target sits so you can do the swap without scanning.

If you can draw the array, draw the map with arrows pointing from values to indices, and trace one remove operation showing the swap, you can rebuild the entire solution from scratch.

Related posts

• LRU Cache - combining data structures for O(1) operations
• Design Twitter - data structure design problems
• Two Sum - hash map for O(1) lookups