380.Insert_Delete_GetRandom_O(1)(Medium).md

380. Insert Delete GetRandom O(1) (Medium)

Date and Time: Sep 12, 2024, 23:23 (EST)

Link: https://leetcode.com/problems/insert-delete-getrandom-o1/

Question:

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.

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:
RandomizedSet randomizedSet = new RandomizedSet();
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^31 <= val <= 2^31 - 1

• At most 2 * 10^5 calls will be made to insert, remove, and getRandom.

• There will be at least one element in the data structure when getRandom is called.

Walk-through:

In order to insert and remove in $O(1)$ time, we need a hashmap{} and list[] to keep track.

Insert: We insert val in self.hashmap{} with the current length of list[]. Then, we append val into list[].

Remove: We want to switch the value we need to remove with the last value in self.list, we first get the index by self.hashmap[val], then we access the value's index and replace it with the last value by self.list[idx] = lastVal. Then, we remove the last value in list[] and update the hashmap's last value to idx. Finally, we can remove val from self.hashmap{}.

getRandom: we can use built-in random.choice(self.list) to return element from self.list.

Python Solution:

class RandomizedSet:

    def __init__(self):
        self.hashmap = {}
        self.list = []

    def insert(self, val: int) -> bool:
        if val not in self.hashmap:
            self.hashmap[val] = len(self.list)
            self.list.append(val)
            return True
        return False

    def remove(self, val: int) -> bool:
        # Swap the position of last val in self.list and current val's position in self.list, then remove it from the end
        if val in self.hashmap:
            lastIdx = self.hashmap[self.list[-1]]
            lastVal = self.list[-1]
            curIdx = self.hashmap[val]
            # Swap two vals in list
            self.list[lastIdx], self.list[curIdx] = self.list[curIdx], self.list[lastIdx]
            # Update lastVal in hashmap with curIdx
            self.hashmap[lastVal] = curIdx
            del self.hashmap[val]
            self.list.pop()    # Remove the last val (currVal)
            return True
        else:
            return False

    def getRandom(self) -> int:
        return random.choice(self.list)

Time Complexity: $O(1)$
Space Complexity: $O(n)$, n is all integers that will be added.