[Array] LeetCode 380. Insert Delete GetRandom O(1)

Solution

import random
class RandomizedSet:

    def __init__(self):
        self.data_map = {}
        self.data = []

    def insert(self, val: int) -> bool:

        if val not in self.data_map:
            idx = len(self.data)
            self.data_map[val] = idx
            self.data.append(val)
            return True

        return False

    def remove(self, val: int) -> bool:

        if val not in self.data_map:
            return False

        idx_of_cur_val = self.data_map[val]

        last_element = self.data[-1]

        self.data_map[last_element] = idx_of_cur_val
        self.data[idx_of_cur_val] = last_element
        self.data[-1] = val

        self.data.pop()
        self.data_map.pop(val)

        return True


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

1. The tricky part for this question is the remove() function.
2. We can use a set to remove the val, but we can’t do this since we have to use random.choice(list) for getRandom(), which only supports list type.
3. For the hash map, set the index as the value for the key.
4. Swap the position with the value to be removed and the last element in the array.
5. After swapping the position, use pop() to remove the val from the array.