380. Insert Delete GetRandom O(1)

380

MediumArrays and HashingHash map paired with a dynamic arrayArray + index map with swap-to-end delete

Insert Delete GetRandom O(1)

Design a set that supports insert(val), remove(val), and getRandom, each in average O(1) time. insert returns false if val is already present, true otherwise. remove returns false if val is absent, true otherwise. getRandom returns a uniformly random element currently in the set.

Open official problem prompt ↗

In plain English

Build a container where adding, removing, and picking a uniformly random element are all constant time on average.

Picture it like this

Think of a coat-check rack: the numbered hooks (the list) let you grab a random coat instantly, and a ledger mapping each ticket to its hook number (the map) lets you find any specific coat. When someone leaves, you move the last coat onto their freed hook rather than sliding every coat down.

Example

Input: insert(1); remove(2); insert(2); getRandom(); remove(1); insert(2); getRandom()
Output: [true, false, true, 2, true, false, 2]
Why: insert(1) succeeds; remove(2) fails (absent); insert(2) succeeds; the set is {1,2} so getRandom returns 1 or 2; remove(1) succeeds; insert(2) fails (present); the set is {2} so getRandom must return 2.

Constraints

-2^31 <= val <= 2^31 - 1At most 2 * 10^5 calls total to insert, remove, and getRandomgetRandom is only called when the set has at least one element

Pattern lesson

See the pattern, then code

Array + index map with swap-to-end delete

↗

Arrays and Hashing

Duplicates, frequency counts, grouping, membership tests, or pair lookup.. Store values contiguously in a list so getRandom is one random index, and keep a value->index map so you can locate any value in O(1). To delete without shifting, overwrite the slot with the last element and pop the tail.

New words, made simpleKnow these before the algorithm

Swap-and-pop: Deleting from an array in O(1) by overwriting the target slot with the final element, then removing the final slot.
Amortized O(1): Average constant cost per operation; Python list append/pop at the end are amortized O(1).

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Array only

Locating a value and closing the gap is linear, so remove is too slow.

Store values in a list; remove by scanning for the value and deleting it.

Time O(n) removeSpace O(n)

Hash set only

A set has no positional indexing, so a uniform random pick requires materializing it in O(n).

Store values in a Python set for O(1) insert and remove.

Time O(n) getRandomSpace O(n)

Best choiceList + index map, swap-to-end delete

Every operation is constant time on average and getRandom stays uniform because the list is always dense.

Contiguous list for random access plus a value->index map; delete by swapping the target with the last element.

Time O(1) averageSpace O(n)

The rule we keep true

Invariant

vals is always a gap-free array of exactly the current elements, and idx[v] is the position of v in vals for every present value v.

Why this is correct

Reasoning

getRandom is uniform because vals holds each element exactly once with no holes, so a random index is a uniform choice. remove preserves density: overwriting slot i with the tail element and popping keeps the array contiguous, and updating idx for the moved element keeps the map consistent.

The algorithm in three movesSay these aloud before coding

1Keep a list vals of elements and a dict idx mapping value to its position in vals

vals = [1], idx = {1:0}

2insert: reject if present, else append and record its index

insert(2): vals = [1,2], idx = {1:0, 2:1}

3remove: reject if absent, else move the last element into the removed slot, fix its index, pop the tail, and delete the key

remove(1): move 2 into slot 0 -> vals = [2], idx = {2:0}

4getRandom: pick a random index into vals

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readval=1

2 · AskIs 1 already present?

3 · Update statevals=[1], idx={1:0}

4 · ResultNot present, append -> return true

Key takeaway

vals holds elements contiguously for O(1) random access; idx maps each value to its slot for O(1) locate-and-delete.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 8-13insert
Guard against duplicates, then append to the tail and record its index so future lookups and deletes are O(1).
2
Lines 15-24remove with swap-to-end
Copy the last element into the victim's slot, repoint that element's index, drop the tail, and erase the key so no gap forms.
3
Lines 26-27getRandom
random.choice indexes into a dense list, giving a uniform pick in O(1).

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

Removing the element that is itself last in vals (the swap is a no-op but pop and key deletion still run correctly)
Re-inserting a value that was previously removed
A set with a single element where getRandom must return it

Common beginner mistakes

Forgetting to update idx[last] after moving the last element, leaving a stale index that corrupts later removes
Deleting the key before reading its index
Using list.remove(val), which is O(n) and defeats the purpose
Popping by index in the middle of the list, which shifts elements and breaks O(1)

Check your understanding

Why move the last element into the removed slot instead of the element right after it?

PyPython 3 · solution.py

Optimal

1import random23class RandomizedSet:4    def __init__(self):5        self.idx: dict[int, int] = {}6        self.vals: list[int] = []78    def insert(self, val: int) -> bool:9        if val in self.idx:10            return False11        self.idx[val] = len(self.vals)12        self.vals.append(val)13        return True1415    def remove(self, val: int) -> bool:16        if val not in self.idx:17            return False18        i = self.idx[val]19        last = self.vals[-1]20        self.vals[i] = last21        self.idx[last] = i22        self.vals.pop()23        del self.idx[val]24        return True2526    def getRandom(self) -> int:27        return random.choice(self.vals)

Time complexityO(1) average per operationOptimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMetaMicrosoft

Insert Delete GetRandom O(1)

Insert Delete GetRandom O(1)

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Arrays and Hashing