Insert Delete GetRandom O(1)

LeetCode Q 380 - Insert Delete GetRandom O(1)

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.

Follow up: allow duplicates

Solution

1. First, we consider to use an array to store the inserted number, which costs O(1) time.
2. However, if we want to delete a number from an array, if we want to move the numbers behind this number this will costs nearly O(n) time. Then we consider to swap the last element in the array with the number we want to delete, which is O(1) operation. To realize this operation, we use a HashMap to store the number and corresponding index. So, this map will enable our operation to access each number in the array in O(1) time.
3. Since the numbers are all stored in a consecutive space in the array, from 0 to list.length() - 1, we can use Random.nextInt(list.size()) to get the index, the return the number in that index.

Code:

Map<Integer, Integer> map;
List<Integer> list;
// Initialize your data structure here.
public RandomizedSet() {
	map = new HashMap<>(); list = new ArrayList<>();
}

// 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)) return false;
	map.put(val, list.length());
	list.add(val);
	return true;
}

// Removes a value from the set. Returns true if the set contained the specified element. 
public boolean remove(int val) {
	if (!map.containsKey(val)) return false;
	int index = map.get(val);
	map.put(map.get(list.size() - 1), index);
	list.set(index, lsit.get(list.size() - 1))
	list.remove(list.size() - 1);
	map.remove(val);
}

For the follow-up with duplicates allowed, I think we can use Map(Integer, List(Integer)). Insert would keep adding to the end of the list for duplicates and Remove would try to first remove the last element from the list in map.