381. Insert Delete GetRandom O(1) – Duplicates allowed – Leetcode Solutions

Example 1:

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

class RandomizedCollection:
    def __init__(self):
        # List to store all elements for efficient random access
        self.nums = []
        # Dictionary mapping each value to a set of indices where it appears in nums
        self.indices = defaultdict(set)

    def insert(self, val: int) -> bool:
        # Check if the value is new to the collection (i.e., has no prior indices)
        is_new_element = len(self.indices[val]) == 0
        
        # Append the value to the nums list and store its index
        self.nums.append(val)
        self.indices[val].add(len(self.nums) - 1)
        
        # Return True if this was the first occurrence of val, otherwise False
        return is_new_element

    def remove(self, val: int) -> bool:
        # If val is not present, we cannot remove it
        if not self.indices[val]:
            return False

        # Get an index of val from the set of indices
        remove_idx = self.indices[val].pop()
        last_val = self.nums[-1]

        # Replace val at remove_idx with the last element if they are different
        if remove_idx != len(self.nums) - 1:
            self.nums[remove_idx] = last_val
            # Update the index set for last_val to include remove_idx and remove the old index
            self.indices[last_val].add(remove_idx)
            self.indices[last_val].discard(len(self.nums) - 1)

        # Remove the last element from nums and indices
        self.nums.pop()

        # If val has no more occurrences, remove it from indices entirely
        if not self.indices[val]:
            del self.indices[val]

        return True

    def getRandom(self) -> int:
        # Return a random element from nums
        return random.choice(self.nums)

class RandomizedCollection {
public:
    // Constructor to initialize the collection
    RandomizedCollection() {}

    // Insert a value into the collection
    bool insert(int val) {
        bool is_new = val_to_indices[val].empty(); // Check if `val` is a new entry
        values.push_back(val); // Add `val` to the `values` list
        val_to_indices[val].insert(values.size() - 1); // Store the index of `val`
        return is_new;
    }

    // Remove one occurrence of a value from the collection
    bool remove(int val) {
        // If `val` is not in the collection, return false
        if (val_to_indices[val].empty()) return false;

        // Get the index of `val` to remove
        int idx_to_remove = *val_to_indices[val].begin();
        
        // Remove index from `val_to_indices`
        val_to_indices[val].erase(idx_to_remove);
        
        // Get the last element in `values` and its index
        int last_val = values.back();
        int last_idx = values.size() - 1;

        // Replace `val` at `idx_to_remove` with `last_val`
        values[idx_to_remove] = last_val;

        // Update index tracking for `last_val`
        val_to_indices[last_val].insert(idx_to_remove);
        val_to_indices[last_val].erase(last_idx);
        
        // Remove the last element from the vector
        values.pop_back();

        // Clean up `val_to_indices` for `val` if it's empty
        if (val_to_indices[val].empty()) {
            val_to_indices.erase(val);
        }
        
        return true;
    }

    // Get a random value from the collection
    int getRandom() {
        // Generate a random index from 0 to `values.size() - 1`
        int random_idx = rand() % values.size();
        return values[random_idx];
    }

private:
    std::vector<int> values; // Store values for quick access
    std::unordered_map<int, std::unordered_set<int>> val_to_indices; // Map each value to its set of indices
};

var RandomizedCollection = function() {
    // Initialize the collection as an array to store values and a map to store indices of each value.
    this.values = [];
    this.indices = new Map(); // { value: Set of indices }
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.insert = function(val) {
    // Check if val is already in the collection
    let alreadyExists = this.indices.has(val);

    // Add the index of the new value in the indices map
    if (!alreadyExists) {
        this.indices.set(val, new Set());
    }
    this.indices.get(val).add(this.values.length);
    
    // Insert the value into the values array
    this.values.push(val);

    // Return true if it was a new entry, false otherwise
    return !alreadyExists;
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.remove = function(val) {
    // If val is not in the collection, return false
    if (!this.indices.has(val) || this.indices.get(val).size === 0) {
        return false;
    }

    // Get an arbitrary index of val from the indices map
    let removeIndex = this.indices.get(val).values().next().value;

    // Remove the index from the set for val
    this.indices.get(val).delete(removeIndex);

    // If removing last element, just pop
    let lastIndex = this.values.length - 1;
    if (removeIndex !== lastIndex) {
        let lastVal = this.values[lastIndex];
        
        // Move the last value to the position of the value to remove
        this.values[removeIndex] = lastVal;
        
        // Update the indices map for the last value
        this.indices.get(lastVal).delete(lastIndex);
        this.indices.get(lastVal).add(removeIndex);
    }

    // Remove the last element from the values array
    this.values.pop();

    // If no more instances of val remain, delete it from indices map
    if (this.indices.get(val).size === 0) {
        this.indices.delete(val);
    }

    return true;
};

/**
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function() {
    // Generate a random index and return the value at that index
    let randomIndex = Math.floor(Math.random() * this.values.length);
    return this.values[randomIndex];
};

class RandomizedCollection {

    // List to store the values of the collection.
    private List<Integer> values;
    
    // Map to store indices of each value in the collection.
    // Key is the value, and value is a set of indices where the key appears in the `values` list.
    private Map<Integer, Set<Integer>> indicesMap;
    
    // Random object for generating random indices.
    private Random random;

    // Constructor to initialize the data structures.
    public RandomizedCollection() {
        values = new ArrayList<>();
        indicesMap = new HashMap<>();
        random = new Random();
    }

    // Inserts a value into the collection.
    // Returns true if it was not already present; false otherwise.
    public boolean insert(int val) {
        // Check if the value is new to the collection.
        boolean isNew = !indicesMap.containsKey(val);
        
        // Add value to the values list.
        values.add(val);
        
        // Add the index of the new value to the map.
        indicesMap.putIfAbsent(val, new HashSet<>());
        indicesMap.get(val).add(values.size() - 1);
        
        return isNew;
    }

    // Removes one occurrence of a value from the collection if it exists.
    // Returns true if the value was present and removed; false otherwise.
    public boolean remove(int val) {
        // If the value is not in the collection, return false.
        if (!indicesMap.containsKey(val) || indicesMap.get(val).isEmpty()) {
            return false;
        }

        // Get an index of the value to remove from the set of indices.
        int removeIdx = indicesMap.get(val).iterator().next();
        
        // Remove this index from the indices map.
        indicesMap.get(val).remove(removeIdx);

        // If the removed index is not the last element, swap it with the last element.
        if (removeIdx < values.size() - 1) {
            int lastVal = values.get(values.size() - 1);
            
            // Move the last element to the removed index.
            values.set(removeIdx, lastVal);
            
            // Update the indices map for the swapped element.
            indicesMap.get(lastVal).remove(values.size() - 1);
            indicesMap.get(lastVal).add(removeIdx);
        }

        // Remove the last element in the list, which is now a duplicate if we swapped.
        values.remove(values.size() - 1);

        // Clean up the indices map if no indices remain for `val`.
        if (indicesMap.get(val).isEmpty()) {
            indicesMap.remove(val);
        }

        return true;
    }

    // Returns a random element from the collection.
    public int getRandom() {
        // Get a random index within the bounds of the `values` list.
        int randomIndex = random.nextInt(values.size());
        
        // Return the value at the random index.
        return values.get(randomIndex);
    }
}