# 381. Insert Delete GetRandom O(1) - Duplicates allowed

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FUsXKnO62ccXb8dnS2XOl%2Fimage.png?alt=media\&token=8ae8b37c-c5ec-4aa1-a85a-31b5987929c7)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FjsztUtxdq1dNXgcrUBdt%2Fimage.png?alt=media\&token=7966e8f0-010b-44c0-b5be-14b0848ea3f3)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FPmYfRK0DIH6ZEUG3riTK%2Fimage.png?alt=media\&token=13580c2c-9bd0-490f-a855-e4bc0419a5c5)

time: all O(1)

space: O(1\~n)

```java
class RandomizedCollection {
    
    private List<Integer> nums;
    private Map<Integer, Set<Integer>> map; // use set to store multi indexs
    private Random rand;
    
    public RandomizedCollection() {
        nums = new ArrayList<>();
        map = new HashMap<>();
        rand = new Random();
    }
    
    public boolean insert(int val) {
        boolean result = !map.containsKey(val); // this is tricky...
        
        map.computeIfAbsent(val, k -> new HashSet<>());
        map.get(val).add(nums.size()); // add (val, num.size())
        nums.add(val); // add nums in list
        return result;
    }
    
    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        
        Set<Integer> deleteIndexs = map.get(val);
        
        // if remove middle position in muti indexs(sets)
        if (!deleteIndexs.contains(nums.size()-1)) { // lastnum put into dele...
            int deleteIndex = deleteIndexs.iterator().next(); // get one of indexs from sets to delete 
            int lastNum = nums.get(nums.size()-1); // the last number
            
            nums.set(deleteIndex, lastNum);
            
            map.get(lastNum).remove(nums.size()-1); // remove origin index
            map.get(lastNum).add(deleteIndex); // change to deleteIndex
            map.get(val).remove(deleteIndex); // remove delete val
        }
        
        // if remove last position
        map.get(val).remove(nums.size()-1);// remove map(val, last position index)
        if (map.get(val).size() == 0) { // if set is empty, directly remove 
            map.remove(val);
        }
        nums.remove(nums.size()-1); // remove last num in list
        return true;
    }
    
    public int getRandom() {
        return nums.get(rand.nextInt(nums.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();
 */
```