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

Problem Statement

Design a data structure that supports all the following operations in average O(1) time. Note that duplicates are allowed.

Implement the RandomizedCollection class:

• bool insert(int val):
  Inserts an item val into the collection. Returns true if the collection did not already contain val.

• bool remove(int val):
  Removes an occurrence of val from the collection if present. Returns true if the collection contained val.

• int getRandom():
  Returns a random element from the current collection of elements. The probability of each element being returned is linearly related to the number of that element in the collection.

Important:

• Since duplicates are allowed, the same value can appear multiple times.
• The getRandom method should return one element chosen uniformly at random from the multiset of all elements.

Example

Example 1:

Input:
  RandomizedCollection collection = new RandomizedCollection();
  collection.insert(1);    // Returns true as 1 was not present.
  collection.insert(1);    // Returns false since 1 is already present (but it is still inserted).
  collection.insert(2);    // Returns true; 2 was not present.
  collection.getRandom();  // Should return 1 with probability 2/3, and 2 with probability 1/3.
  collection.remove(1);    // Returns true; one occurrence of 1 is removed.
  collection.getRandom();  // Now both 1 and 2 should have equal probability of being returned.

Explanation:

1. After the first insert, the collection is: [1]
2. After inserting 1 again, the collection becomes: [1, 1]
3. After inserting 2, the collection is: [1, 1, 2]
4. The getRandom method returns one of these elements with a probability proportional to its frequency.
5. Removing one occurrence of 1 changes the collection to: [1, 2]

Hints

1. Storing Elements:
   Use a dynamic array (like a Python list or Java ArrayList) to store the elements. This allows for fast random access (needed for getRandom) and fast appending.

2. Handling Duplicates:
   To support duplicates and enable O(1) removals, use a hash map that maps a value to a set (or list) of indices in the array where that value occurs.

3. Removal Trick:
   When removing an element, swap the element to be removed with the last element in the array (if it isn’t already the last element), update the indices in the hash map for the swapped element, and then remove the last element. This avoids shifting elements and keeps the removal operation O(1).

Detailed Approach

Data Structures Used:

• List (or Array):
  Store all the elements inserted. This is used for getRandom.

• HashMap (or Dictionary):
  Map each value to a set (or a HashSet) of indices in the list where that value appears. This allows us to know quickly where each value is located in the list.

Operations:

1. Insert(val):

   • Append the value to the list.
   • Add the new index (list’s last index) to the set of indices for that value in the hash map.
   • Return true if this is the first occurrence of the value (i.e. if the set was empty before insertion), false otherwise.

2. Remove(val):

   • Check if the value exists in the hash map and if its index set is not empty.
   • Remove (and obtain) an arbitrary index from the set.
   • Get the last element in the list.
   • Swap the element at the removed index with the last element if they are different.
   • Update the hash map for the last element to reflect its new index.
   • Remove the last element from the list.
   • If the set of indices for val becomes empty, remove it from the hash map.
   • Return true if removal was successful.

3. GetRandom():

   • Generate a random index within the bounds of the list.
   • Return the element at that index.

Step-by-Step Walkthrough

Assume we start with an empty collection.

1. Insert(1):

   • List becomes: [1]
   • Map: {1: {0}}
   • Returns true because 1 was not already present.

2. Insert(1):

   • List becomes: [1, 1]
   • Map: {1: {0, 1}}
   • Returns false since 1 was already in the collection.

3. Insert(2):

   • List becomes: [1, 1, 2]
   • Map: {1: {0, 1}, 2: {2}}
   • Returns true since 2 was not present.

4. GetRandom():

   • Random index between 0 and 2 is chosen.
   • Returns 1 with probability 2/3 (if index 0 or 1) or 2 with probability 1/3 (if index 2).

5. Remove(1):

   • Remove one occurrence of 1 from the map (say, index 0).
   • Swap the last element (which is 2) into index 0.
   • List becomes: [2, 1] (after removal, and the last element is removed).
   • Update the map:
     • For 1: remove index 0, now remains {1} (the index for the remaining 1, which might be at index 1 if it wasn’t moved).
     • For 2: update index from 2 to 0.
   • Returns true.

6. GetRandom():

   • Now the list is [2, 1]. Both values appear once.
   • Randomly returns either 2 or 1 with equal probability.

Code Implementation

Python Code