Insert Delete GetRandom O(1) - Duplicates allowed

Problem Statement

The RandomizedCollection is a versatile data structure designed to manage a collection of integers, where duplicates are allowed. This multiset supports multiple operations: adding new values (with duplicates permitted), removing existing values, and randomly selecting a value from the set. The design must ensure that each operation—specifically insert, remove, and getRandom—operates with an average time complexity of O(1).

• insert(int val): Inserts a value into the collection. Returns true if the value was not already present; otherwise, returns false.
• remove(int val): Removes one occurrence of a value from the collection. Returns true if the value existed; otherwise, returns false.
• getRandom(): Returns a random element from the collection. Each element's probability of being returned is proportional to its frequency.

Examples

Example 1

Input:

["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"]
[[], [1], [1], [2], [], [1], []]

Output:

[null, true, false, true, 2, true, 1]

Explanation:

RandomizedCollection collection = new RandomizedCollection();
collection.insert(1);       // Returns true, inserted first 1
collection.insert(1);       // Returns false, 1 already present
collection.insert(2);       // Returns true, inserted 2
collection.getRandom();     // Returns 1 (2/3 chance) or 2 (1/3 chance)
collection.remove(1);       // Returns true, removes one 1
collection.getRandom();     // Returns 1 or 2, each has 50% chance

Constraints

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

Approach and Intuition

1. Data Structure Design:

   • Use a list to store all elements.
   • Use a hash map to store a set of indices for each value.

2. Insert Operation:

   • Append the value to the list.
   • Add the new index to the map under that value.
   • Return true if it’s the first insertion of that value, otherwise false.

3. Remove Operation:

   • If the value is not present in the map, return false.
   • Get any index of the value from the map.
   • Swap this index with the last element in the list (if it’s not already the last).
   • Update the map entries for the swapped value.
   • Remove the last element from the list.
   • If no indices remain for the removed value, delete it from the map.
   • Return true.

4. getRandom Operation:

   • Choose a random index in the list using randrange.
   • Return the element at that index.

By combining a list for fast random access and a dictionary for efficient index tracking and updating, the structure ensures O(1) average time complexity for all required operations. This design supports efficient multiset behavior with randomization.

Solutions

public class RandomizedSet {
    ArrayList<Integer> elements;
    HashMap<Integer, Set<Integer>> indexes;
    java.util.Random random = new java.util.Random();

    public RandomizedSet() {
        elements = new ArrayList<Integer>();
        indexes = new HashMap<Integer, Set<Integer>>();
    }

    public boolean insert(int value) {
        if (!indexes.containsKey(value)) indexes.put(value, new LinkedHashSet<Integer>());
        indexes.get(value).add(elements.size());
        elements.add(value);
        return indexes.get(value).size() == 1;
    }

    public boolean remove(int value) {
        if (!indexes.containsKey(value) || indexes.get(value).isEmpty()) return false;
        int removeIndex = indexes.get(value).iterator().next();
        indexes.get(value).remove(removeIndex);
        int lastElement = elements.get(elements.size() - 1);
        elements.set(removeIndex, lastElement);
        indexes.get(lastElement).add(removeIndex);
        indexes.get(lastElement).remove(elements.size() - 1);

        elements.remove(elements.size() - 1);
        return true;
    }

    public int getRandom() {
        return elements.get(random.nextInt(elements.size()));
    }
}