DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Insert Delete GetRandom O(1)

mediumArrays and hashing Must-do

Problem statement

Design a class called RandomizedSet that behaves like a set of distinct integers, but supports three operations, each running in average O(1) time:

  • insert(val) — add val to the set if it isn't already there. Return true if it was added, false if it was already present.
  • remove(val) — take val out of the set if it's there. Return true if it was removed, false if it wasn't present.
  • getRandom() — return a random element currently in the set. Every element must be equally likely to come back, and getRandom is only ever called when the set has at least one element.

The tricky part is getRandom: a plain hash set gives you fast insert and remove, but it doesn't let you jump to "a random one of these" in constant time. You need a structure that supports all three operations quickly at once.

A real-world version of this: imagine a pool of healthy backend instances that servers get inserted into when they pass a health check and removed from when they fail one, and a load balancer needs to pick one instance at random from the pool for every incoming request, instantly.

Examples

Example 1

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) succeeds (set is now {1}). remove(2) fails since 2 isn't in the set. insert(2) succeeds (set is now {1, 2}). getRandom() can return either 1 or 2 — here it returns 2. remove(1) succeeds (set is now {2}). insert(2) fails because 2 is already present. With only 2 left in the set, the final getRandom() must return 2.

Hints

Approach

Optimal: Hash map + swap-and-pop array

Intuition

The better approach's weakness was that a hash set has no "position" to look up for getRandom. The fix is to keep the array from the brute force (so getRandom stays O(1)) and a hash map from value to its index in that array (so insert and remove no longer need to scan). The one remaining problem is removal: deleting from the middle of an array normally means shifting everything after it, which is O(n).

The trick that makes removal O(1) is to not care about order. To remove an element, swap it with whatever is currently the last element in the array, then shrink the array by one (removing from the end is always O(1)). Update the hash map so the swapped element now points at its new position. The removed value's slot is gone, and nothing else had to move.

Steps

  1. Keep an array values (all current elements, in no particular order) and a hash map indexOf from value to its position in values.
  2. insert(val): if indexOf already has val, return false. Otherwise record indexOf[val] = len(values), append val to values, and return true.
  3. remove(val): if indexOf doesn't have val, return false. Otherwise:
    • Look up idx = indexOf[val] and let lastVal be the last element of values.
    • Overwrite values[idx] with lastVal, and update indexOf[lastVal] = idx.
    • Remove the now-duplicated last slot from values, and delete val from indexOf.
    • Return true.
  4. getRandom(): pick a random index between 0 and len(values) - 1 and return values at that index.

Dry run

Following Example 1, showing values and indexOf after each call:

call values before result values after indexOf after
insert(1) [] true [1] {1: 0}
remove(2) [1] false [1] {1: 0}
insert(2) [1] true [1, 2] {1: 0, 2: 1}
getRandom() [1, 2] 2 (or 1) [1, 2] unchanged
remove(1): swap values[0] (the 1) with the last element 2, then drop the last slot [1, 2] true [2] {2: 0}
insert(2) [2] false [2] {2: 0}
getRandom() [2] 2 [2] unchanged

Edge cases: removing the last element in the array is a special case worth checking on paper — you'd be "swapping" an element with itself, which is harmless (the swap and the index update just leave things as they were), then you shrink the array by one as usual.

Complexity

Time O(1) — average for all three operations. `insert` appends to the end of an array (O(1) amortized) and adds one hash map entry. `remove` looks up the element's index in O(1), then swaps it with the last array element and shrinks the array by one — both O(1) — instead of shifting everything after it. `getRandom` picks a random valid array index and returns that element directly, O(1).

Space O(n) — one array slot and one hash map entry per element currently in the set.

import random


class RandomizedSet:
    def __init__(self):
        self.values: list[int] = []
        self.index_of: dict[int, int] = {}

    def insert(self, val: int) -> bool:
        if val in self.index_of:
            return False
        self.index_of[val] = len(self.values)
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.index_of:
            return False
        idx = self.index_of[val]
        last_val = self.values[-1]
        self.values[idx] = last_val
        self.index_of[last_val] = idx
        self.values.pop()
        del self.index_of[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.values)


def fmt(x):
    return str(x).lower() if isinstance(x, bool) else str(x)


if __name__ == "__main__":
    random.seed(0)
    rs = RandomizedSet()
    print(fmt(rs.insert(1)))    # true
    print(fmt(rs.remove(2)))    # false
    print(fmt(rs.insert(2)))    # true
    print(fmt(rs.getRandom()))  # 2 (or 1)
    print(fmt(rs.remove(1)))    # true
    print(fmt(rs.insert(2)))    # false
    print(fmt(rs.getRandom()))  # 2

Follow-up questions

Change indexOf to map each value to a set of indices instead of a single index (in Python, dict[int, set[int]]). insert appends to values as before and adds the new index to that value's index set. remove deletes one occurrence: pick any index from the value's index set, swap that array slot with the last element (updating the swapped element's index set), then remove the used index. All three operations stay O(1) average; the only change is that each value can own more than one array slot.

A single in-memory array and hash map no longer fit on one machine, so you'd shard by hashing the value to pick which machine owns it — insert and remove route to the owning shard and behave exactly as before locally. getRandom is the harder part: picking uniformly across shards of different sizes means either weighting the random shard choice by each shard's current size (which requires tracking sizes centrally) or accepting an approximately-uniform result by picking a random shard first and then a random element within it.

RecapThe whole problem in a few lines, for the night before
  • Spot it: a data structure that needs O(1) insert, remove, *and* a uniformly random element
  • Idea: keep the values in an array (for O(1) random-index access) plus a hash map from value to its array index (for O(1) lookup); remove by swapping with the last element and shrinking the array
  • Cost: O(1) average time for every operation, O(n) space
  • Trap: removing from the middle of a plain array shifts every later element — always O(n) — unless you swap the target with the last element first

Frequently asked questions

That's close to the better approach above, and it still leaves you with an O(n) getRandom unless the list and the map stay in sync with positions, not just membership. The optimal approach's key idea is storing the array index as the map's value, not just true — that's what lets remove jump straight to the spot that needs to change instead of searching for it.

Removing from the end of an array is always O(1) — no other elements need to move. So instead of removing an element from wherever it happens to sit (which would require shifting everything after it), we first swap it into the last position, then remove from there. The hash map has to be updated for the one element that got swapped, but that's a single O(1) update, not a shift of the whole array.

LeetCode requires a genuinely uniform choice — every currently-present element must have an equal chance of being returned. Picking a uniformly random index into the backing array and returning that element satisfies this, since every element occupies exactly one array slot at all times.

Interviewers use it to check whether a candidate can combine two data structures to get properties that neither one gives alone — the same skill needed to design a connection pool, a cache with fast eviction, or a pool of healthy nodes that a load balancer samples from at random. It also tests whether you can reason carefully about an in-place swap without introducing an off-by-one bug.