In this problem, We have to design a data structure that supports Insert, Delete, and GetRandom in average O(1) time.
OR
Design a data structure that supports insert, delete, and getRandom in constant time O(1).
insert(value): Inserts an item value to the set if it’s not present.
remove(value): Removes an item value 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.
For Example –
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// 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(); |
In this problem, we have to implement insert, remove and get random operations in O(1). Let’s first think which data structure should we use to implement all of the three methods in O(1).
Let’s consider few data structures and see whether we able to solve this problem using these data structures.
i) By using HashMap or HashSet
The first choice comes to our mind is to use HashMap or HashSet. By using HashMap or HashSet we can insert and remove in O(1) but what about getRandom() method. To implement getRandom() we have to choose random index and return the element present at that index, which is not possible using HashMap or HashSet.
ii) By using ArrayList
What about ArrayList, Can we solve this problem using ArrayList? By using ArrayList we can implement insert() and getRandom() method in O(1) but what about remove() method.
Now, we are clear that by using these data structures alone, we won’t be able to implement all the three operations in O(1). To solve this problem we have to use both HashMap and ArrayList.
Programming Question on Binary Tree
Insert Delete GetRandom O(1) using HashMap and ArrayList – Java Code
We can solve this problem by using HashMap and ArrayList. The idea here is to first insert each element in an ArrayList and in HashMap we put the element and its index (Element index which is present in ArrayList).
Insert() Method Implementation
If element which we are going to insert is already present in a Map then we simply return false. Else we first add this element in an ArrayList and then we put the element and its index in a Map.
Remove() Method
If an element is not present in a Map then simply return false. Else first get the index value of this element from a map. Swap the value present at that index with the last element of the ArrayList. Then delete the last element and update the swapped element’s new index in a Map.
GetRandom() Method
We can use the Random class getInt() method, in which we pass the list size.
Let’s write it’s java code.
Insert delete getrandom O(1) video tutorial
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
//Insert, Delete, GetRandom in O(1) public class RandomizedSet { private Map<Integer, Integer> elemIndexMap; private List<Integer> lst; private Random rand; //Constructor public RandomizedSet() { elemIndexMap = new HashMap<>(); lst = new ArrayList<>(); rand = new Random(); } public boolean insert(int val) { if (!elemIndexMap.containsKey(val)) { lst.add(val); elemIndexMap.put(val, lst.size() - 1); return true; } return false; } public boolean remove(int val) { if (!elemIndexMap.containsKey(val) ) return false; int indexToRemove = elemIndexMap.get(val); int lastElement = lst.get(lst.size() - 1); lst.set(indexToRemove, lastElement); elemIndexMap.put(lastElement, indexToRemove); elemIndexMap.remove(val); lst.remove(lst.size() - 1); return true; } public int getRandom() { return lst.get(rand.nextInt(lst.size())); } } |
