380. Insert Delete GetRandom O(1)

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

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. 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:
we can use hashing to support the delete insert function. to implement getRandom , we simply get a random number from 0 to size - 1. random.nextInt(size)-size is exclusive.
1.The Map contains the mapping between the value and its index in the ArrayList. The Map helps to check whether a value is already inserted or not and find the swap index in the array.
2. to implement remove function in O(1) time need to swap the last element with the element to remove. ArrayList's remove method is O(n) if you remove from random location. To overcome that, we swap the values between (randomIndex, lastIndex) and always remove the entry from the end of the list. After the swap, you need to update the new index of the swapped value (which was previously at the end of the list) in the map.After swap, remove the element (to delete) from the map and arrayList, change the index of the element which is originally the last element. 3 operations.

    HashMap<Integer, Integer> map;
    ArrayList<Integer> arr;
    public Ex380RandomizedSet() {
        map = new HashMap<Integer,Integer>();
        arr = new ArrayList<Integer>();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if(!map.containsKey(val)){
            map.put(val,arr.size());
            arr.add(val);
            return true;
        }else{
            return false;
        }
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if(map.containsKey(val)){

                // there is 1 element remaining, just remove the element from map and array
         if(arr.size() == 1) {
          map.remove(val);
          arr.remove(0);
         }else {
             int index = map.get(val);
             int lastValue = arr.get(arr.size() - 1);
             swap(arr,index, arr.size()-1);
             map.put(lastValue,index);//change the original last element index
             arr.remove(arr.size()-1);
             map.remove(val);//need to remove the val in the map.
         }
            return true;
        }else{
            return false;
        }
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        Random random = new Random();
        int next = random.nextInt(arr.size());
        return arr.get(next);
        
    }
    private void swap(ArrayList<Integer> arr, int i, int j){
        int temp = arr.get(i);
        arr.set(i, arr.get(j));
        arr.set(j, temp);
    }

Map with getRandom:

public class RandomMap {
    private final Map<Integer, Integer> keyToIndex = new HashMap<>();
    private final List<Entry> entries = new ArrayList<>();

    public void put(int key, int value) {
        if (keyToIndex.containsKey(key)) {
            Entry entry = entries.get(keyToIndex.get(key));
            entry.value = value;
        } else {
            keyToIndex.put(key, entries.size());
            entries.add(new Entry(key, value));
        }
    }

    public Integer get(int key) {
        Integer at = keyToIndex.get(key);
        return at != null ? entries.get(at).value : null;
    }

    public Integer getRandom() {
        if (entries.isEmpty()) return null;
        int at = ThreadLocalRandom.current().nextInt(entries.size());
        return entries.get(at).value;
    }

    public void remove(int key) {
        if (entries.isEmpty() || !keyToIndex.containsKey(key)) return;

        int curr = keyToIndex.get(key);
        int last = entries.size() - 1;

        if (curr != last) {
            Collections.swap(entries, curr, last);
            Entry entry = entries.get(curr);
            keyToIndex.replace(entry.key, curr);
        }

        entries.remove(last); // remove last element O(1)
        keyToIndex.remove(key);
    }

    private static class Entry {
        int key;
        int value;

        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

}