# Q55 Insert Delete GetRandom O(1) - Duplicates allowed - LeetCode

Tue Jan 31 2023 14:02:32 GMT+0000 (UTC)

Saved by @Ayush_dabas07

```class RandomizedCollection {
//we will be using hashset instead of arraylist as there are duplicates,so order
//will get jumbled when we remove and swap elements and we wont have last index
//in the end of the arraylist

HashMap<Integer,HashSet<Integer>> map ;
List<Integer> arr;
Random r;

public RandomizedCollection() {
map = new HashMap<>();
arr = new ArrayList<>();
r = new Random();           //to generate random index
}

public boolean insert(int val) {

//if value exists update its hashset and also AL
if(map.containsKey(val)){
return false;
}

//else make new hashset and add index and add in AL
map.put(val , new HashSet<>());
return true;
}

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

//get any index of value from the hashset and remove it
int index = 0;
for(int idx : map.get(val)){
index = idx;
map.get(val).remove(idx);
break;
}
//if hashset becomes empty remove from map
if(map.get(val).size()==0)
map.remove(val);

if(index == arr.size()-1)   //if its on last index already we can remove in O(1)
arr.remove(index);

else{
int swapped = arr.get(arr.size()-1);    //store swapped value

//swapping and removing in O(1)
arr.set(index,arr.get(arr.size()-1));
arr.remove(arr.size()-1);

//updating swapped values hashset
map.get(swapped).remove(arr.size());    //removing previous index
}

return true;
}

public int getRandom() {
int ri = r.nextInt(arr.size());  //random index

return arr.get(ri);
}
}

/**
* 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();
*/```
content_copyCOPY

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/