233. Insert Delete GetRandom O(1) - Duplicates allowed

Store all elements in a flat array for O(1) random access. A map from value to the set of positions where it lives lets insert/remove be O(1): to remove, swap the target with the last element and pop, fixing up the moved element's index in the map.

Array for random, map for lookup

• arr — a flat list of all elements (duplicates included). getRandom picks a uniform index → probability proportional to multiplicity.
• idx[val] — a set of indices in arr where val currently sits.

insert(val)

Append val to arr, add its index to idx[val]. Return true iff this is the first occurrence.

remove(val) — the swap trick

To delete in O(1) without shifting, swap the target with the last element and pop:

if idx[val] empty: return False
i = idx[val].pop()            # some position holding val
last = arr[-1]
arr[i] = last                 # move last element into the hole
idx[last].add(i); idx[last].discard(len(arr)-1)
arr.pop()
return True

The index bookkeeping keeps idx consistent after the swap.

Worked example

insert(5) → true; getRandom → 5; insert(5) → false (already present); remove(5) → true; now {5} remains; getRandom → 5. Results [null, true, 5, false, true, 5].

Complexity

• Time: O(1) average per operation.
• Space: O(n).

import java.util.*;

class RandomizedCollection {
    private List<Integer> arr;
    private Map<Integer, Set<Integer>> idx;
    private Random rand;

    public RandomizedCollection() {
        arr = new ArrayList<>();
        idx = new HashMap<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        arr.add(val);
        idx.computeIfAbsent(val, z -> new LinkedHashSet<>()).add(arr.size() - 1);
        return idx.get(val).size() == 1;
    }

    public boolean remove(int val) {
        Set<Integer> positions = idx.get(val);
        if (positions == null || positions.isEmpty()) return false;
        int i = positions.iterator().next();
        positions.remove(i);
        int lastIdx = arr.size() - 1;
        int last = arr.get(lastIdx);
        arr.set(i, last);
        Set<Integer> lastPos = idx.get(last);
        lastPos.add(i);
        lastPos.remove(lastIdx);
        arr.remove(lastIdx);
        return true;
    }

    public int getRandom() {
        return arr.get(rand.nextInt(arr.size()));
    }
}