Insert Delete GetRandom O(1)

Medium· design· hash map

Problem

Design a set of integers that supports insert, remove and getRandom, each in average O(1) time. getRandom must return each current element with equal probability.

Examples

Input: insert(1), insert(2), remove(1), getRandom()

Output: true, true, true, 2

After removing 1, the only element left is 2, so getRandom must return it.

Constraints

• -2^31 <= val <= 2^31 - 1
• Up to 2 * 10^5 calls
• getRandom is only called when the set is non-empty

Hints & approach

Hint 1

A hash set gives O(1) insert and remove, but not O(1) uniform random access.

Hint 2

An array gives O(1) random access, but removing from the middle is slow.

Hint 3

Combine them: remove by swapping the target with the last array element, then popping.

Approachtry the hints first

Keep a dynamic array of values and a hash map from value to its index in the array. Insert appends to the array and records the index. Remove looks up the index, moves the last element into that slot, updates the moved element's index in the map, then pops the array and deletes the value from the map. getRandom picks a uniformly random index into the array.

Time O(1) average per operation · Space O(n)

← PreviousLongest Consecutive Sequence Next →4Sum II