Hash map + array for O(1) random

37 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You run a club and keep the member list on index cards. Three things happen all day: a new member joins, a member leaves, and the committee asks you to pick a member at random for a prize. Picking at random is easy if the cards are in a numbered stack: roll a die, take that card. Removing a member is easy if you know where their card is, but if a card leaves the middle of the stack every card behind it shifts, and the numbers on the cards are now wrong. Looking up where a member's card is means reading through the stack. We want all three operations to be instant.

Build the structure, one piece at a time

Piece one is an array, the numbered stack. Random access is "pick a random index between 0 and size − 1". Insert is "append at the end". Both take constant time. Remove is the problem.

Piece two is a hash map from value to its index in the array, so finding where a value lives is one lookup instead of a scan. Inserting 1, 2, 3 gives:

Piece three is the trick that makes removal constant time. Deleting from the middle of an array shifts everything after it. But nobody cares about the order of the members, so instead of shifting, swap the doomed value with the last value, then pop the last slot. To remove 2: the map says 2 is at index 1; the last value is 3 at index 2; swap them so the array is [1, 3, 2]; update the map so 3 points at index 1; pop the tail and delete 2 from the map:

getRandom() now picks index 0 or 1 with equal chance and returns 1 or 3.

Why it is correct

The invariant is that the map holds exactly the values in the array, and map[v] is the index where v currently sits. Insert appends at index size and records that index, so the invariant holds. Remove changes the position of exactly one surviving value, the former tail, and it updates that value's map entry in the same step, before popping; the removed value is dropped from both. getRandom reads an index from 0 to size − 1, every one of which holds a live member, and all are equally likely.

The one subtle case is removing the last element itself: the swap is with itself and nothing moves, which the same code handles without a special branch.

Why it is fast

Insert is one hash insert and one append: O(1) on average. Remove is one hash lookup, one swap, one hash update, one pop and one hash delete: O(1) on average. getRandom is one random number and one array read: O(1). Against the index-card stack, whose removal shifts up to n cards and whose lookup reads up to n cards, every operation went from O(n) to O(1). The memory is one array slot and one map entry per member, O(n).

Why not a hash set alone? A set gives O(1) insert and remove but no way to pick a random element without walking it, because its slots are mostly empty. Why not an array alone? Random and append are fine but remove needs a search. Each half covers the other's weakness.

How to recognise it in an interview

Cues: "all operations in O(1)", "getRandom", "pick a random element", "remove by value", "design a data structure that supports…". Say: "an array for random access plus a hash map from value to index, and I remove by swapping with the last element so nothing shifts".

Insert Delete GetRandom O(1) is the structure above exactly. The duplicates variant keeps, for each value, a set of the indices where it appears, and the swap updates the set of the value that moved. Design Underground System is the same habit of pairing hash maps so that each query is one lookup: one map for in-progress trips keyed by passenger, another for totals keyed by the station pair.

02The idea in one line

Array for random access, map from value to its index; delete by swapping with the last.

Reach for it when: Insert delete getRandom, with duplicates, random set designs.

Cost: O(1) per op.

03The walk-through, step by step

The video works one example: RandomizedSet: insert 1, 2, 3; remove 2; getRandom. These are its captions in order, so you can follow without the video or check a step you missed.

1. Array gives random index access; map gives O(1) lookup of an element's slot
2. insert(1): append at index 0, map[1] = 0
3. insert(2): append at index 1, map[2] = 1
4. insert(3): append at index 2, map[3] = 2
5. remove(2): deleting from the middle would shift everything
6. So swap 2 with the last element 3: map[3] = 1
7. Pop the tail and drop 2 from the map: still O(1)
8. getRandom(): random index in [0, size) → say index 1 = 3
9. insert, remove, getRandom all O(1) average

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Design: Hash map + doubly linked list (LRU), Time-versioned map, Lazy iterators, Ordered intervals (range module), Streaming data structures.