# Insert Delete GetRandom O(1) - Duplicates allowed
**Difficulty:** HARD
[External](https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed)
Canonical: https://scaleengineer.com/dsa/problems/insert-delete-getrandom-o(1)-duplicates-allowed
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Design](https://scaleengineer.com/dsa/patterns/design), [Randomized](https://scaleengineer.com/dsa/patterns/randomized)
**Data structures:** Array, Hash Table
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin), [Yelp](https://scaleengineer.com/companies/yelp), [Zeta](https://scaleengineer.com/companies/zeta), [Citadel](https://scaleengineer.com/companies/citadel), [Affirm](https://scaleengineer.com/companies/affirm), [Peloton](https://scaleengineer.com/companies/peloton)
---
## 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:

* `RandomizedCollection()` Initializes the empty `RandomizedCollection` object.
* `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 is 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 elements. The probability of each element being returned is **linearly related** to the number of the same values the multiset contains.

You must implement the functions of the class such that each function works on **average** `O(1)` time complexity.

**Note:** The test cases are generated such that `getRandom` will only be called if there is **at least one** item in the `RandomizedCollection`.

**Example 1:**

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

**Explanation**
RandomizedCollection randomizedCollection = new RandomizedCollection();
randomizedCollection.insert(1);   // return true since the collection does not contain 1.
                                  // Inserts 1 into the collection.
randomizedCollection.insert(1);   // return false since the collection contains 1.
                                  // Inserts another 1 into the collection. Collection now contains [1,1].
randomizedCollection.insert(2);   // return true since the collection does not contain 2.
                                  // Inserts 2 into the collection. Collection now contains [1,1,2].
randomizedCollection.getRandom(); // getRandom should:
                                  // - return 1 with probability 2/3, or
                                  // - return 2 with probability 1/3.
randomizedCollection.remove(1);   // return true since the collection contains 1.
                                  // Removes 1 from the collection. Collection now contains [1,2].
randomizedCollection.getRandom(); // getRandom should return 1 or 2, both equally likely.

**Constraints:**

* `-231 <= val <= 231 - 1`
* At most `2 * 105` 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.

# Approaches
## Brute Force with ArrayList
This approach uses a simple `ArrayList` to store the elements of the collection. While this makes `getRandom` very efficient, the `insert` and `remove` operations suffer from linear time complexity because they require searching through the list.
**Time:** `insert`: O(N)
`remove`: O(N)
`getRandom`: O(1)

Where N is the number of elements in the collection. · **Space:** O(N), where N is the number of elements in the collection, to store the elements in the list.
**Pros:** Simple to understand and implement.; `getRandom` is highly efficient with O(1) time complexity.
**Cons:** `insert` and `remove` operations have a time complexity of O(N), which fails to meet the problem's requirement of average O(1) time complexity for all functions.
### Explanation
We use a `java.util.ArrayList<Integer>` to store all the numbers in the collection, including duplicates.

*   **`insert(val)`**: To check if the element was already present (as required for the return value), we must scan the list using `list.contains(val)`, which takes O(N) time. Then, adding the element to the end of the list is an amortized O(1) operation. The overall complexity is dominated by the search, making it O(N).

*   **`remove(val)`**: To remove an element, we use the `ArrayList.remove(Object o)` method. This method first needs to find the element, which takes O(N) time. After finding it, it removes the element and shifts all subsequent elements one position to the left to fill the gap, which also takes O(N) time in the worst case. Thus, the total time complexity is O(N).

*   **`getRandom()`**: This is the strong point of this approach. We can generate a random integer between 0 and the list's size minus one. Accessing an element at a random index in an `ArrayList` is an O(1) operation.

```java
class RandomizedCollection {
    List<Integer> list;
    Random rand;

    public RandomizedCollection() {
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        boolean notPresent = !list.contains(val);
        list.add(val);
        return notPresent;
    }

    public boolean remove(int val) {
        // Note: This removes the first occurrence of val.
        return list.remove(Integer.valueOf(val));
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}
```
### Algorithm
*   Initialize an `ArrayList` `list` and a `Random` object.
*   For `insert(val)`:
    1.  Check if `val` is in `list` using `list.contains(val)`. This is an O(N) operation.
    2.  Add `val` to `list`.
    3.  Return the result of the check from step 1.
*   For `remove(val)`:
    1.  Call `list.remove(Integer.valueOf(val))` which finds and removes the first occurrence of `val`. This involves a search (O(N)) and a potential shift of elements (O(N)).
    2.  Return the boolean result from the `remove` call.
*   For `getRandom()`:
    1.  Generate a random index from `0` to `list.size() - 1`.
    2.  Return the element at that index.

## Optimal Approach with HashMap and ArrayList
This optimal approach combines the strengths of a `HashMap` for fast lookups and an `ArrayList` for O(1) random access. This allows all three operations (`insert`, `remove`, `getRandom`) to be performed in average O(1) time, even with duplicate elements.
**Time:** `insert`: O(1)
`remove`: O(1)
`getRandom`: O(1)

All complexities are on average, due to hash map operations and amortized time for ArrayList additions. · **Space:** O(N), where N is the total number of elements. The `list` stores N elements, and the `map` stores U unique elements as keys, with a total of N indices stored across all the sets.
**Pros:** Achieves the required average O(1) time complexity for all operations.; Efficiently handles duplicate elements.
**Cons:** More complex to implement and debug compared to a simpler approach.; Uses more memory due to the overhead of the `HashMap` and `Set` objects.
### Explanation
The core idea is to use two data structures:
1.  An `ArrayList` (`list`) to store all the elements. This allows for O(1) `getRandom` by picking a random index.
2.  A `HashMap<Integer, Set<Integer>>` (`map`) where keys are the element values and values are `Set`s of indices where that element appears in the `list`. This allows for O(1) lookup of an element's locations. We use a `LinkedHashSet` for the set to ensure we can get an element (the first one) from it in O(1) time.

*   **`insert(val)`**: We check if `val` is a key in our `map` to determine the return value. We then add `val` to the end of the `list` and add its new index (`list.size() - 1`) to the set of indices associated with `val` in the `map`. All these steps are average O(1).

*   **`remove(val)`**: This is the most intricate part. A naive removal from the `list` would be O(N). To achieve O(1), we use a swap-and-pop strategy:
    1.  Get an index of `val` to remove, `idxToRemove`, from its corresponding set in the `map`.
    2.  Get the last element in the `list`, `lastElement`, and its index, `lastIdx`.
    3.  Move `lastElement` to the position `idxToRemove` in the `list`.
    4.  Remove the last element from the `list` (which is now a duplicate of the element at `idxToRemove`). This is an O(1) operation.
    5.  Update the `map` to reflect these changes: remove `idxToRemove` from `val`'s index set, and for `lastElement`, remove `lastIdx` and add `idxToRemove` to its index set. This logic correctly handles all cases, including when the element to be removed is the last element or when it's the same as the last element.

*   **`getRandom()`**: We generate a random index and return the element from the `list` at that index. This is O(1).

```java
class RandomizedCollection {
    private List<Integer> list;
    private Map<Integer, Set<Integer>> map;
    private Random rand = new Random();

    public RandomizedCollection() {
        list = new ArrayList<>();
        map = new HashMap<>();
    }

    public boolean insert(int val) {
        boolean notPresent = !map.containsKey(val);
        map.computeIfAbsent(val, k -> new LinkedHashSet<>()).add(list.size());
        list.add(val);
        return notPresent;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }

        Set<Integer> valIndices = map.get(val);
        int idxToRemove = valIndices.iterator().next();

        int lastIdx = list.size() - 1;
        int lastElement = list.get(lastIdx);

        list.set(idxToRemove, lastElement);
        valIndices.remove(idxToRemove);

        Set<Integer> lastElementIndices = map.get(lastElement);
        if (idxToRemove != lastIdx) {
            lastElementIndices.remove(lastIdx);
            lastElementIndices.add(idxToRemove);
        }

        if (valIndices.isEmpty()) {
            map.remove(val);
        }

        list.remove(lastIdx);

        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}
```
### Algorithm
*   Initialize an `ArrayList` `list`, a `HashMap<Integer, Set<Integer>>` `map`, and a `Random` object.
*   For `insert(val)`:
    1.  Check if `map` contains `val` to determine the return value.
    2.  Add `val` to the end of `list`. The new index is `list.size() - 1`.
    3.  Add the new index to the `Set` associated with `val` in the `map`.
*   For `remove(val)`:
    1.  If `val` is not in `map`, return `false`.
    2.  Get an index `idxToRemove` from the `Set` of indices for `val`.
    3.  Get the last element `lastElement` and its index `lastIdx` from `list`.
    4.  Replace the element at `idxToRemove` in `list` with `lastElement`.
    5.  Remove `idxToRemove` from the index set for `val`.
    6.  If `idxToRemove` is not the last index, update the index set for `lastElement`: remove `lastIdx` and add `idxToRemove`.
    7.  If the index set for `val` is now empty, remove `val` from the `map`.
    8.  Remove the last element from `list`.
    9.  Return `true`.
*   For `getRandom()`:
    1.  Generate a random index from `0` to `list.size() - 1`.
    2.  Return the element at that index from `list`.

# Solutions
### Java

```java
class RandomizedCollection { private Map < Integer , Set < Integer >> m ; private List < Integer > l ; private Random rnd ; /** Initialize your data structure here. */ public RandomizedCollection () { m = new HashMap <>(); l = new ArrayList <>(); rnd = new Random (); } /** * Inserts a value to the collection. Returns true if the collection did not already contain * the specified element. */ public boolean insert ( int val ) { m . computeIfAbsent ( val , k -> new HashSet <>()). add ( l . size ()); l . add ( val ); return m . get ( val ). size () == 1 ; } /** * Removes a value from the collection. Returns true if the collection contained the specified * element. */ public boolean remove ( int val ) { if (! m . containsKey ( val )) { return false ; } Set < Integer > idxSet = m . get ( val ); int idx = idxSet . iterator (). next (); int lastIdx = l . size () - 1 ; l . set ( idx , l . get ( lastIdx )); idxSet . remove ( idx ); Set < Integer > lastIdxSet = m . get ( l . get ( lastIdx )); lastIdxSet . remove ( lastIdx ); if ( idx < lastIdx ) { lastIdxSet . add ( idx ); } if ( idxSet . isEmpty ()) { m . remove ( val ); } l . remove ( lastIdx ); return true ; } /** Get a random element from the collection. */ public int getRandom () { int size = l . size (); return size == 0 ? - 1 : l . get ( rnd . nextInt ( size )); } } /** * Your RandomizedCollection object will be instantiated and called as such: * RandomizedCollection obj = new RandomizedCollection(); * boolean param_1 = obj.insert(val); * boolean param_2 = obj.remove(val); * int param_3 = obj.getRandom(); */
```

### Python

```python
from collections import defaultdict from random import choice class RandomizedCollection : # official solution def __init__ ( self ): """ Initialize your data structure here. """ self . lst = [] self . dict = defaultdict ( set ) # change from 381 (with no duplicates) def insert ( self , val : int ) -> bool : """ Inserts a value to the collection. Returns true if the collection did not already contain the specified element. """ self . dict [ val ]. add ( len ( self . lst )) self . lst . append ( val ) return len ( self . dict [ val ]) == 1 ''' >>> a = set([1,1,2,3]) >>> a {1, 2, 3} >>> a.pop() 1 >>> a {2, 3} ''' def remove ( self , val : int ) -> bool : """ Removes a value from the collection. Returns true if the collection contained the specified element. """ if not self . dict [ val ]: return False remove_index , last_val = self . dict [ val ]. pop (), self . lst [ - 1 ] # pop() on a set self . lst [ remove_index ] = last_val self . dict [ last_val ]. add ( remove_index ) self . dict [ last_val ]. discard ( len ( self . lst ) - 1 ) self . lst . pop () return True def getRandom ( self ) -> int : """ Get a random element from the collection. """ return choice ( self . lst ) # Your RandomizedCollection object will be instantiated and called as such: # obj = RandomizedCollection() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom()
```