Randomized Set

Implement RandomizedSet that supports insert, remove, and getRandom in O(1) average time. getRandom returns a random element with equal probability.

Example 1

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

Solution Approach

Use a HashMap (val→index) and a List (for O(1) random access). On remove, swap with last element.

Map map; List list.
insert: if not in map, add to list, map[val]=list.size()-1.
remove: if in map, swap val with last element (update last element's map entry), remove from list and map.
getRandom: return list[random index].

Java

import java.util.*;

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

    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        list.add(val); map.put(val, list.size()-1); return true;
    }
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int idx = map.get(val), last = list.get(list.size()-1);
        list.set(idx, last); map.put(last, idx);
        list.remove(list.size()-1); map.remove(val); return true;
    }
    public int getRandom() { return list.get(rand.nextInt(list.size())); }
}

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