Problem

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.

remove(val): Removes an item val from the set if present.getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.Example:

// Init an empty set.

RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.

randomSet.insert(1);

// Returns false as 2 does not exist in the set.

randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].

randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.

randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].

randomSet.remove(1);

// 2 was already in the set, so return false.

randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.

randomSet.getRandom();

Solution

class RandomizedSet {    Map
    
      map;    List
     
       list;    public RandomizedSet() {        map = new HashMap<>();        list = new ArrayList<>();    }        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) {        int index = map.getOrDefault(val, -1);        if (index == -1) return false;        //swap val with the tail element in list        Collections.swap(list, index, list.size()-1);                //update the swapped tail element in map        map.put(list.get(index), index);                //remove val from the tail of list, remove val from map        list.remove(list.size()-1);        map.remove(val);        return true;    }        public int getRandom() {        int max = list.size();        int min = 0;        int index = (int)(Math.random() * (max-min) + min);        return list.get(index);    }}
     
    

Allow Duplicates

LC381