Coding Interview PatternsInsert Delete GetRandom O(1) - Duplicates Allowed
HardCustom Data Structures

Insert Delete GetRandom O(1) - Duplicates Allowed

Explanation & Solution

Practice Problem

Description

Design a data structure that supports inserting and removing integers (including duplicates) and returning a random element, all in O(1) average time. Each element must have equal probability of being returned by getRandom.

Implement a function that processes an array of operations and an array of arguments:

  • "RandomizedCollection" — Initializes the collection.
  • "insert" — Inserts val into the collection. Returns true if val was not already present, false if it was.
  • "remove" — Removes one occurrence of val from the collection. Returns true if val was present, false otherwise.
  • "getRandom" — Returns a random element. Each element (including duplicates) must have equal probability.
Input:operations = ["RandomizedCollection","insert","insert","insert","remove","getRandom"], args = [[],[1],[1],[2],[1],[]]
0
RandomizedCollection
1
insert
2
insert
3
insert
4
remove
5
getRandom
Output:[null,true,false,true,true,1]
0
null
1
true
2
false
3
true
4
true
5
1

Explanation: Insert 1 (new→true), insert 1 again (dup→false), insert 2 (new→true). Remove one 1 (→true). Collection is [1,2]. getRandom must return 1 (only one left if 2 wasn't the answer — here collection has equal 1s and 2s; getRandom=1 in this deterministic test).

Constraints

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

Approach

Custom Data Structures pattern

1. Array + Map of Index Sets

  • list: stores all values (including duplicates) for O(1) random access
  • valToIdx: maps value → Set<indices> — all positions where that value appears in list

2. Implement Insert

  • Track whether the value existed before (for the return value)
  • Add the new index (list.length) to valToIdx[val]
  • Append val to list

3. Implement Remove — The Swap Trick

  • Pick any index of val from valToIdx[val] (use the first one)
  • Swap list[removeIdx] with list[lastIdx] (the last element)
  • Update valToIdx[lastVal]: remove lastIdx, add removeIdx
  • Pop the last element from list
  • Remove removeIdx from valToIdx[val]

4. Handle the Edge Case: Removing the Last Element

  • If removeIdx === lastIdx, the value to remove IS the last element
  • Skip the swap step — just pop and remove the index

5. GetRandom

  • Pick a random index from list using Math.random()
  • Since list holds all occurrences, duplicates have proportional probability automatically

Key Insight

  • The set of indices per value (instead of a single index as in the non-duplicate version) handles multiple occurrences
  • The swap-and-pop trick maintains O(1) removal without shifting elements
Time
O(1) average for all operations
Space
O(n) where n is total insertions

Solution Code

Previous
All O(1) Data Structure