Insert Delete GetRandom O(1) - Duplicates allowed

Hard· design· hash map

Problem

Design a multiset that supports insert, remove (one occurrence) and getRandom in average O(1) time. Duplicates are allowed, and getRandom must pick each stored occurrence with equal probability, so a value stored twice is twice as likely.

Examples

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

Output: true, false, true, 1 with probability 2/3 or 2 with probability 1/3

insert returns true only when the value was not already present.

Constraints

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

Hints & approach

Hint 1

Start from the no-duplicates version: an array plus a value -> index map.

Hint 2

A value can now live at many indices, so map it to a set of indices.

Hint 3

When you swap the last element into a hole, update that element's index set too.

Approachtry the hints first

Store every occurrence in a dynamic array, and keep a map from value to the set of indices where it occurs. Insert appends and adds the new index to the value's set. Remove takes any index i from the value's set, moves the array's last element into position i, fixes the moved value's index set (remove the old last index, add i), then pops the array. getRandom returns the element at a uniformly random array index, which weights values by their multiplicity.

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

← Previous4Sum II DoneBack to Hashing & maps