Insert Delete GetRandom O(1)
Problem Description
Implement the RandomizedSet class:
RandomizedSet()Initializes theRandomizedSetobject.bool insert(int val)Inserts an itemvalinto the set if not present. Returnstrueif the item was not present,falseotherwise.bool remove(int val)Removes an itemvalfrom the set if present. Returnstrueif the item was present,falseotherwise.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.
Example 1:
Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]
Explanation
Constraints:
- -231 <= val <= 231 - 1
- At most
2 * 105calls will be made toinsert,remove, andgetRandom. - There will be at least one element in the data structure when
getRandomis called.
Solve it on LeetCode
Approaches
1. List and HashSet
Intuition:
We can use a combination of a list and a set to achieve the operations required by the problem. The list allows us to efficiently access and remove elements with the help of an index, while the set ensures that we don't insert duplicate elements, owing to its unique property. However, removing an element from the middle of the list is an O(n) operation, which doesn't meet the optimal constraint, but it is a stepping stone towards understanding the problem.
Code:
- Time Complexity:
O(n)forremove(), andO(1)forinsert()andgetRandom(). - Space Complexity:
O(n)for storingnelements in the list and set.
2. HashMap and ArrayList
Intuition:
To achieve O(1) on all operations, we can use a combination of a HashMap to store elements and their indices, and an ArrayList to store the elements. The HashMap gives us O(1) access and removal time when handling key-value pairs, while the ArrayList provides O(1) time for random access. The trick to efficiently remove an element from the list is to swap the element to remove with the last element, then remove the last element. This approach retains the order only up to the end where the swap happens, which is acceptable since we only need getRandom to return any element.
Code:
- Time Complexity:
O(1)for all operations (insert(),remove(),getRandom()). - Space Complexity:
O(n)for storingnelements in the map and list.