Problem Description

The problem is to design a data structure that supports the following operations in average O(1) time, even when duplicate elements are allowed:

• insert(val): Inserts an item val into the collection. Returns true if the item was not already present (i.e., this is the first occurrence), or false otherwise.
• remove(val): Removes one occurrence of val from the collection if present. Returns true if the item was present and removed, or false otherwise.
• getRandom(): Returns a random element from the collection. Each element (including duplicates) must have the same probability of being returned.

The key constraints are:

• Duplicates are allowed in the collection.
• All operations (insert, remove, getRandom) must work in average O(1) time.

Thought Process

At first glance, supporting O(1) insertions and deletions with duplicates seems challenging. Using a simple list (array) makes getRandom() easy (since we can pick a random index), but removing a specific value is slow (O(n)), especially with duplicates. Using a hash map allows for fast lookups, but it doesn't support random access or efficient duplicate management.

To get all operations to O(1), we need a hybrid approach. The main idea is to use a dynamic array (list) for quick random access and a hash map to track all positions of each value, even when duplicates exist. This way, we can insert and remove in O(1) by always removing from the array's end and updating the hash map accordingly.

Solution Approach

Here’s a step-by-step breakdown of the optimized solution:

1. Use a List/Array: Store all inserted elements in a list (or array). This allows O(1) random access for getRandom().
2. Use a Hash Map of Sets: Maintain a hash map (dictionary) where each key is a value in the collection, and the value is a set of indices in the list where that value occurs. This lets us track all occurrences of duplicates.
3. Insert Operation: Append the new value to the list. Add the index to the set in the hash map. If the value was not in the map before, return true; otherwise, false.
4. Remove Operation:
   • If the value is not in the map or its set is empty, return false.
   • Otherwise, remove an arbitrary index for this value from its set.
   • Swap the last element in the list with the element at this index (unless it's already the last element).
   • Update the sets in the map to reflect the new index of the swapped element.
   • Remove the last element from the list (since it’s now duplicated or moved).
   • If the set for the removed value is now empty, remove the key from the map.
5. getRandom Operation: Pick a random index in the list and return the value at that index.

This design ensures every operation is O(1) on average, even with duplicates.

Example Walkthrough

Let's walk through an example:

• insert(1) → List: [1], Map: {1: {0}}
• insert(1) → List: [1, 1], Map: {1: {0, 1}}
• insert(2) → List: [1, 1, 2], Map: {1: {0, 1}, 2: {2}}
• getRandom() → Returns 1 or 2 (with probability proportional to their counts)
• remove(1):
  • Pick index 0 (arbitrary) for 1. Swap with last element (2): List: [2, 1, 1]
  • Update indices in map: 2 now at index 0, 1 at indices 1, 2
  • Remove last element: List: [2, 1], Map: {1: {1}, 2: {0}}
• getRandom() → Returns 2 or 1 (each with 50% probability)

Notice how the map tracks all indices for duplicates, and how the swap-and-pop method keeps removals O(1).

Time and Space Complexity

• Brute-force approach:
  • Using only a list, insert is O(1), but remove is O(n) (need to search for value), and getRandom is O(1).
• Optimized approach:
  • insert: O(1) — append to list, add to set in map
  • remove: O(1) — remove index from set, swap/pop in list, update map
  • getRandom: O(1) — random index in list
  • Space: O(n) — storing all elements and their indices

Summary

This solution elegantly combines a dynamic array (for O(1) random access) and a hash map of sets (for O(1) tracking of all value positions, even with duplicates). The clever use of swap-and-pop for removals and careful index bookkeeping enables all required operations to be performed in average O(1) time, meeting the problem’s constraints. This approach demonstrates the power of combining standard data structures to solve complex requirements efficiently.

Code Implementation

import random
from collections import defaultdict

class RandomizedCollection:

    def __init__(self):
        self.nums = []
        self.idx = defaultdict(set)

    def insert(self, val: int) -> bool:
        self.nums.append(val)
        self.idx[val].add(len(self.nums) - 1)
        return len(self.idx[val]) == 1

    def remove(self, val: int) -> bool:
        if not self.idx[val]:
            return False
        remove_idx = self.idx[val].pop()
        last_val = self.nums[-1]
        self.nums[remove_idx] = last_val
        if self.idx[last_val]:
            self.idx[last_val].add(remove_idx)
            self.idx[last_val].discard(len(self.nums) - 1)
        self.nums.pop()
        return True

    def getRandom(self) -> int:
        return random.choice(self.nums)
      

#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <cstdlib>

class RandomizedCollection {
public:
    std::vector<int> nums;
    std::unordered_map<int, std::unordered_set<int>> idx;

    RandomizedCollection() {}

    bool insert(int val) {
        nums.push_back(val);
        idx[val].insert(nums.size() - 1);
        return idx[val].size() == 1;
    }

    bool remove(int val) {
        if (idx[val].empty()) return false;
        int remove_idx = *idx[val].begin();
        idx[val].erase(remove_idx);
        int last_val = nums.back();
        nums[remove_idx] = last_val;
        idx[last_val].insert(remove_idx);
        idx[last_val].erase(nums.size() - 1);
        nums.pop_back();
        return true;
    }

    int getRandom() {
        int rand_idx = rand() % nums.size();
        return nums[rand_idx];
    }
};
      

import java.util.*;

class RandomizedCollection {
    List<Integer> nums;
    Map<Integer, Set<Integer>> idx;
    Random rand;

    public RandomizedCollection() {
        nums = new ArrayList<>();
        idx = new HashMap<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        boolean notPresent = !idx.containsKey(val) || idx.get(val).isEmpty();
        idx.computeIfAbsent(val, k -> new HashSet<>()).add(nums.size());
        nums.add(val);
        return notPresent;
    }

    public boolean remove(int val) {
        if (!idx.containsKey(val) || idx.get(val).isEmpty()) return false;
        int removeIdx = idx.get(val).iterator().next();
        idx.get(val).remove(removeIdx);
        int lastVal = nums.get(nums.size() - 1);
        nums.set(removeIdx, lastVal);
        idx.get(lastVal).add(removeIdx);
        idx.get(lastVal).remove(nums.size() - 1);
        nums.remove(nums.size() - 1);
        return true;
    }

    public int getRandom() {
        return nums.get(rand.nextInt(nums.size()));
    }
}
      

var RandomizedCollection = function() {
    this.nums = [];
    this.idx = new Map();
};

RandomizedCollection.prototype.insert = function(val) {
    if (!this.idx.has(val)) this.idx.set(val, new Set());
    this.idx.get(val).add(this.nums.length);
    this.nums.push(val);
    return this.idx.get(val).size === 1;
};

RandomizedCollection.prototype.remove = function(val) {
    if (!this.idx.has(val) || this.idx.get(val).size === 0) return false;
    let removeIdx = this.idx.get(val).values().next().value;
    this.idx.get(val).delete(removeIdx);
    let lastVal = this.nums[this.nums.length - 1];
    this.nums[removeIdx] = lastVal;
    if (this.idx.has(lastVal)) {
        this.idx.get(lastVal).add(removeIdx);
        this.idx.get(lastVal).delete(this.nums.length - 1);
    }
    this.nums.pop();
    return true;
};

RandomizedCollection.prototype.getRandom = function() {
    return this.nums[Math.floor(Math.random() * this.nums.length)];
};