Arrays - Insert Delete Get Random O(1)

Implement the RandomizedSet class:

RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Input: Operations order ["insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[1], [2], [2], [], [1], [2], []]
Output: [true, false, true, 2, true, false, 2]
Explanation:
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints:

-2³¹ <= val <= 2³¹ - 1
At most 2 * 10⁵ calls will be made to insert, remove, and getRandom.

Solution 1 - Using a HashMap to have Insert() and Remove() operations in O(1) time, and a List to track current elements and to have Get() operation in O(1) time

In this approach, we are going to use a HashMap to store elements as well as into an ArrayList. The reason we are storing elements into a HashMap is because we need to be able to insert() and remove() operation in O(1) time. But, we need to have getRandom() operation also run in O(1) time, so for this reason, we are going to store elements into an ArrayList as well, and the index of the element is stored and retrieved from the HashMap.

Implementation details:

Initialize a ArrayList that we are going to store elements into, call it numbers, a HashMap that we are going to use it to store elements and key and index as value, call it numberToIndex.
insert() operation: If the numberToIndex already contains the input element, return false, otherwise add it to the numbers as well as to numberToIndex and return true.
remove() operation: If the numberToIndex doesn't contains the input element, return false, otherwise check the index of the element from numberToIndex and if this is the last element in numbers, then remove it from numbers and numberToIndex. If the index of the element is not the end index, then we will replace that element with end element in numbers, and update end element indexed element to current index in numberToIndex. Then, remove end element from numbers and remove input element from numberToIndex.
The reason we do this is because, if the element is not at the end, then removing an element will require resizing of the array and this is O(n) operation, so instead or removing the element, we replace that with end indexed element and remove that end element, and update the end element index in the numberToIndex to reflect it.
getRandom() operation: To get random number within the range of numbers indexes range, we will use java.util.Random class's nextInt(int bound) method, and return that random indexed element from numbers.

import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Random; public class InsertDeleteGetRandom { final HashMap<Integer, Integer> numberToIndex; final List<Integer> numbers; final Random randomGen; public InsertDeleteGetRandom() { numberToIndex = new HashMap<>(); numbers = new ArrayList<>(); randomGen = new Random(); } public boolean insert(int val) { if(numberToIndex.containsKey(val)) { return false; } numberToIndex.put(val, numbers.size()); numbers.add(val); return true; } public boolean remove(int val) { if(!numberToIndex.containsKey(val)) { return false; } int index = numberToIndex.get(val); int lastIndex = numbers.size()-1; if(index != lastIndex) { // re-arrange numbers // update the index for last element of list in the map // replace the element that we are going tot delete with the last element in the List int lastElement = numbers.get(lastIndex); numbers.set(index, lastElement); numberToIndex.put(lastElement, index); } numbers.remove(lastIndex); numberToIndex.remove(val); return true; } public int getRandom() { int random = randomGen.nextInt(numbers.size()); return numbers.get(random); } public static void main(String[] args) { InsertDeleteGetRandom insertDeleteGetRandom = new InsertDeleteGetRandom(); System.out.println(insertDeleteGetRandom.insert(1)); System.out.println(insertDeleteGetRandom.remove(2)); System.out.println(insertDeleteGetRandom.insert(2)); System.out.println(insertDeleteGetRandom.getRandom()); System.out.println(insertDeleteGetRandom.remove(1)); System.out.println(insertDeleteGetRandom.insert(2)); System.out.println(insertDeleteGetRandom.getRandom()); insertDeleteGetRandom = new InsertDeleteGetRandom(); System.out.println(insertDeleteGetRandom.remove(0)); System.out.println(insertDeleteGetRandom.remove(0)); System.out.println(insertDeleteGetRandom.insert(0)); System.out.println(insertDeleteGetRandom.getRandom()); System.out.println(insertDeleteGetRandom.remove(0)); System.out.println(insertDeleteGetRandom.insert(0)); System.out.println(insertDeleteGetRandom.getRandom()); } }

Complexity Analysis:

Time complexity: Above code runs in O(1) time for all operations insert(), remove() and getRandom().
Space complexity: O(n), since we are storing elements into a HashMap and an ArrayList.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation details:

Complexity Analysis: