Randomized Collection

Like RandomizedSet but allows duplicates. All three operations must be O(1) on average.

Example 1

insert(1)→true, insert(1)→false, insert(2)→true, getRandom()→1or2, remove(1)→true, getRandom()→1or2

Solution Approach

Use a Map> and a List. On remove, swap with last element, update set of indices for both elements.

Map> map; List list.
insert: add to list, add index to map[val].
remove: pick any index i for val; swap with last element; update indices; remove.

Java

import java.util.*;

class RandomizedCollection {
    Map<Integer, LinkedHashSet<Integer>> map = new HashMap<>();
    List<Integer> list = new ArrayList<>();
    Random rand = new Random();

    public boolean insert(int val) {
        boolean absent = !map.containsKey(val) || map.get(val).isEmpty();
        map.computeIfAbsent(val, k->new LinkedHashSet<>()).add(list.size());
        list.add(val); return absent;
    }
    public boolean remove(int val) {
        if (!map.containsKey(val) || map.get(val).isEmpty()) return false;
        int idx = map.get(val).iterator().next();
        int last = list.get(list.size()-1);
        map.get(val).remove(idx);
        if (idx < list.size()-1) {
            list.set(idx, last);
            map.get(last).remove(list.size()-1);
            map.get(last).add(idx);
        }
        list.remove(list.size()-1); return true;
    }
    public int getRandom() { return list.get(rand.nextInt(list.size())); }
}

Time Complexity: All O(1) average
Space Complexity: O(N)