Insert delete getrandom o1 duplicates allowed

Array Hash Table Math Design Randomized

36.4% acceptance

Jan 12, 2026

2421

159

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::collections::{HashMap, HashSet};

struct RandomizedCollection {
  map: HashMap<i32, HashSet<usize>>,
  vec: Vec<i32>,
}

impl RandomizedCollection {
  fn new() -> Self {
    RandomizedCollection {
      map: HashMap::new(),
      vec: Vec::new(),
    }
  }
  
  fn insert(&mut self, val: i32) -> bool {
    let is_new = !self.map.contains_key(&val);
    self.map.entry(val).or_insert_with(HashSet::new).insert(self.vec.len());
    self.vec.push(val);
    is_new
  }
  
  fn remove(&mut self, val: i32) -> bool {
    if let Some(indices) = self.map.get_mut(&val) {
      let idx = *indices.iter().next().unwrap();
      indices.remove(&idx);
      
      if indices.is_empty() {
        self.map.remove(&val);
      }
      
      let last_idx = self.vec.len() - 1;
      
      // Only swap if we're not removing the last element
      if idx != last_idx {
        let last_val = self.vec[last_idx];
        self.vec[idx] = last_val;
        
        // Update the index of the last value
        if let Some(last_indices) = self.map.get_mut(&last_val) {
          last_indices.remove(&last_idx);
          last_indices.insert(idx);
        }
      }
      
      self.vec.pop();
      true
    } else {
      false
    }
  }
  
  fn get_random(&self) -> i32 {
    use std::collections::hash_map::RandomState;
    use std::hash::{BuildHasher, Hash, Hasher};
    
    let state = RandomState::new();
    let mut hasher = state.build_hasher();
    self.vec.len().hash(&mut hasher);
    let hash = hasher.finish();
    let idx = (hash as usize) % self.vec.len();
    self.vec[idx]
  }
}