Insert Delete GetRandom O(1) — The Array+HashMap Design Trick

Problem Statement#

Implement the RandomizedSet class:

• RandomizedSet() — Initializes the RandomizedSet object.
• bool insert(int val) — Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) — Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() — Returns a random element from the current set of elements. Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Constraints:

• -2^31 <= val <= 2^31 - 1
• At most 2 * 10^5 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:
  ["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
  [[],[1],[2],[2],[],[1],[2],[]]
Output: [null, true, false, true, 2, true, false, 2]
Explanation:
  insert(1)    → true (1 was not present)
  remove(2)    → false (2 was not present)
  insert(2)    → true (2 was not present)
  getRandom()  → 2 (only options: 1 or 2, both equally likely — 2 happened)
  remove(1)    → true (1 was present; set now has only 2)
  insert(2)    → false (2 is already present)
  getRandom()  → 2 (only element)

Why This Problem Matters#

Insert Delete GetRandom O(1) is one of the best design interview problems because it requires you to combine two simple data structures — a dynamic array and a hash map — in a non-obvious way to achieve three different O(1) guarantees simultaneously. Google and Meta include this in their interview loops to see whether candidates can think beyond single data structures and design composite systems.

The problem exposes a fundamental tension: hash maps give O(1) insert and delete but no way to get a truly uniform random element (you cannot index into a hash map). Arrays give O(1) index access (for getRandom) but O(n) deletion (shifting elements). Neither data structure alone satisfies all three requirements.

The key insight — swapping the element to delete with the last element, then popping the last position — transforms O(n) array deletion into O(1). This "swap and pop" trick is fundamental to many competitive programming problems and real-world systems. It appears in heap implementations (heapify-down after swapping root with last), graph algorithms (removing vertices from adjacency lists), and database systems (removing rows from clustered indexes).

Understanding this trick also prepares you for the harder variant: Insert Delete GetRandom O(1) — Duplicates Allowed (LC 381), where you must handle multiple copies of the same value. That problem requires storing a set of indices per value instead of a single index.

The Core Insight#

What each data structure provides:

• Dynamic array (arr): O(1) indexing for getRandom (pick a random index in [0, len-1]). But deleting from the middle is O(n).
• HashMap (idx_map): Maps value to its current index in arr. O(1) insert and lookup. But no random access.

The swap-and-pop trick for O(1) deletion:

To delete value v at index i:

1. Find the last element last = arr[-1].
2. Move last to position i: arr[i] = last.
3. Update the map: idx_map[last] = i.
4. Remove the last position: arr.pop().
5. Delete v from the map: del idx_map[v].

Steps 1–5 are all O(1). The array shrinks by one and v is gone. The relative order of other elements may change, but order does not matter for a set.

Edge case: When v is the last element, last == v. In this case, arr[i] = last assigns the same value to arr[-1], and idx_map[last] = i updates last's index to i — but then del idx_map[v] removes it. This is correct: the assignment and update are no-ops because they are immediately undone by the deletion. The code handles this case without any special branching.

Visual Dry Run#

Capacity operations: insert(1), insert(2), insert(3), remove(2), getRandom()

After insert(1): arr=[1],       map={1:0}
After insert(2): arr=[1,2],     map={1:0, 2:1}
After insert(3): arr=[1,2,3],   map={1:0, 2:1, 3:2}
 
remove(2):
  i = map[2] = 1
  last = arr[-1] = 3
  arr[1] = 3    →  arr=[1,3,3]  (temporarily)
  map[3] = 1    →  map={1:0, 2:1, 3:1}
  arr.pop()     →  arr=[1,3]
  del map[2]    →  map={1:0, 3:1}
 
After remove(2): arr=[1,3], map={1:0, 3:1}
 
getRandom(): pick random index in [0,1]
  → returns arr[0]=1 or arr[1]=3, each with prob 1/2

Solution (Optimal)#

import random
 
class RandomizedSet:
    def __init__(self):
        self.arr = []          # Stores values for O(1) random access
        self.idx_map = {}      # Maps value → index in arr for O(1) lookup
 
    def insert(self, val: int) -> bool:
        if val in self.idx_map:
            return False
        self.arr.append(val)
        self.idx_map[val] = len(self.arr) - 1
        return True
 
    def remove(self, val: int) -> bool:
        if val not in self.idx_map:
            return False
 
        # Swap val with the last element, then pop the last
        i = self.idx_map[val]
        last = self.arr[-1]
 
        self.arr[i] = last
        self.idx_map[last] = i
 
        self.arr.pop()
        del self.idx_map[val]
        return True
 
    def getRandom(self) -> int:
        return random.choice(self.arr)

class RandomizedSet {
    constructor() {
        this.arr = [];       // Dynamic array for O(1) random access
        this.idxMap = new Map();  // value → index in arr
    }
 
    insert(val) {
        if (this.idxMap.has(val)) return false;
        this.arr.push(val);
        this.idxMap.set(val, this.arr.length - 1);
        return true;
    }
 
    remove(val) {
        if (!this.idxMap.has(val)) return false;
 
        const i = this.idxMap.get(val);
        const last = this.arr[this.arr.length - 1];
 
        // Swap val with last element
        this.arr[i] = last;
        this.idxMap.set(last, i);
 
        // Remove last position and val from map
        this.arr.pop();
        this.idxMap.delete(val);
        return true;
    }
 
    getRandom() {
        const idx = Math.floor(Math.random() * this.arr.length);
        return this.arr[idx];
    }
}

Complexity Analysis

All operations are O(1) average. Array pop() and append() are amortized O(1) due to dynamic array resizing.

Common Mistakes#

• Forgetting to update idx_map[last] after the swap. After arr[i] = last, the map still says last → old_index. If you skip idx_map[last] = i, subsequent operations on last (remove or lookup) will have a stale index.
• Deleting val from the map before reassigning last's index. If val == last (removing the last element), you must handle the deletion carefully. The code above handles this correctly: arr[i] = last is a no-op, idx_map[last] = i temporarily updates the index, then del idx_map[val] removes it. No special case needed.
• Using a Python set instead of the array+map combination. Python's built-in set does not support O(1) random element access — random.choice(list(s)) requires O(n) list conversion.
• Off-by-one when storing the index. After arr.append(val), the new element is at len(arr) - 1, not len(arr).
• Not returning the boolean correctly. insert returns True if the element was newly added, False if it was already present (and not added). remove returns True if the element was found and removed, False if it was absent.

Follow-up Questions#

What if duplicates are allowed? (LC 381) Store a set of indices per value in the map: idx_map[val] = set_of_indices. On removal, pick any index from the set, apply the swap-and-pop trick, and update the indices set accordingly. This is significantly more complex but uses the same underlying idea.

Why is random.choice(arr) guaranteed to be uniform? Python's random.choice selects a random index in [0, len-1] with equal probability. Since every element in arr occupies exactly one index, each element is returned with equal probability 1/n.

What if you need weighted random selection (not uniform)? Store weights alongside values. Use a weighted random sampling algorithm (e.g., prefix sums + binary search). This is LC 528 Random Pick with Weight.

How would you make this thread-safe? Wrap all three methods with a lock. For higher concurrency, use read-write locks (shared for getRandom, exclusive for insert and remove).

What if you need to support peek (return random element without removing)? getRandom already does this — it returns a random element without removing it. No additional change is needed.

Key Takeaways#

• LC 380 RandomizedSet requires O(1) insert, remove, and getRandom — a standard library set or list cannot do all three.
• The trick is a hashmap (val -> index) paired with a dynamic array (the values themselves).
• For O(1) remove: swap the target with the last element, pop the array, and update the hashmap index for the swapped value.
• For O(1) getRandom: pick a uniform random index into the array; the array contiguity guarantees uniformity.
• Always update the swapped element's index in the hashmap BEFORE popping — order matters when the target is itself the last element.
• This compound structure (hashmap + array) underlies fair-shuffle reservoirs, ID pools, and online matching systems.
• Extending to duplicates (LC 381) just stores a set of indices per value instead of a single index.

Related Problems#

• LC 380 — Insert Delete GetRandom O(1): This problem.
• LC 381 — Insert Delete GetRandom O(1) — Duplicates Allowed: Extension with duplicate handling using sets of indices per value.
• LC 528 — Random Pick with Weight: Weighted random selection using prefix sums and binary search.
• LC 710 — Random Pick with Blacklist: Select random from range excluding a blacklist — uses a remap trick similar to swap-and-pop.
• LC 432 — All O'one Data Structure: O(1) increment/decrement of counts and O(1) max/min retrieval.
• LC 146 — LRU Cache: Another compound HashMap + linked list design problem.