Skip to main content

381. Insert Delete GetRandom O(1) - Duplicates allowed

hard

Same O(1) contract as the no-duplicates version — insert, remove, random — but the multiset can hold repeats. The fix is one level of indirection: instead of mapping val -> single index, map val -> set of indices. The swap-with-last delete trick now has to update two map entries instead of one, and the bookkeeping is what makes this hard rather than medium.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

RandomizedCollection is a data structure that contains a collection of numbers, possibly duplicates (i.e., a multiset). It should support inserting and removing specific elements and also reporting a random element. Implement the RandomizedCollection class. bool insert(int val) inserts an item val into the multiset, even if the item is already present. Returns true if the item is not present, false otherwise. bool remove(int val) removes an item val from the multiset if present. Returns true if the item was present, false otherwise. Note that if val has multiple occurrences in the multiset, we only remove one of them. int getRandom() returns a random element from the current multiset of items. The probability of each element being returned is linearly related to the number of same values the multiset contains. You must implement the functions of the class such that each function works on average O(1) time complexity.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • At most 2 * 10^5 calls in total will be made to insert, remove, and getRandom.
  • There will be at least one element in the data structure when getRandom is called.

Examples

Example 1

Input
['RandomizedCollection','insert','insert','insert','getRandom','remove','getRandom']
[[],[1],[1],[2],[],[1],[]]
Output
[null,true,false,true,2,true,1]

Explanation: Insert 1 (new -> true), insert 1 again (duplicate -> false), insert 2 (new -> true). getRandom returns 1 with probability 2/3 and 2 with probability 1/3. Remove one 1 (present -> true). Now the multiset is {1, 2}, so getRandom returns each with probability 1/2.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

From the no-duplicates version: array values[] plus map val -> index. Duplicates break this because one val maps to multiple positions.

Hint 2

Promote the map's value type to a set: idx[val] is a set of indices where val sits in values[]. Insert appends and adds to the set; getRandom uses uniform random index.

Hint 3

Remove is the tricky part: pop any index from idx[val] (call it i). Swap values[i] with values[-1], then in idx[values[i]] remove the old index (len-1) and add i. Pop values and clean up empty sets.

Solution approach

Reveal approach

Array + map-of-sets. values is a dynamic array; idx maps val -> set of indices in values. insert(val): record was_new = val not in idx or len(idx[val]) == 0. Append val to values; add (len(values) - 1) to idx[val]. Return was_new. remove(val): if val not in idx or empty, return false. Pop any element i from idx[val]. If i is not the last position, swap values[i] with values[-1], then update idx[values[i]] by removing (len(values) - 1) and adding i. Pop values. If idx[val] is now empty, delete the key (optional but clean). Return true. getRandom: return values[random.randrange(len(values))]. The set-per-key is the moat — it lets you grab any occurrence of val in O(1) while preserving the swap-with-last invariant.

Complexity

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

Related patterns

  • hash-map
  • array-design
  • swap-with-last
  • multiset

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • LinkedIn
  • Two Sigma

Practice these live with InterviewChamp.AI

Drill Insert Delete GetRandom O(1) - Duplicates allowed and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →