deepSWE.io

Insert Delete GetRandom O(1)

Hashing

MediumLeetCode #380

30 min

Problem Statement

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. 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.

Solution (Hash Map + Array)

To achieve O(1) time complexity for all operations, we can use a combination of a hash map and an array. The hash map will store the value and its index in the array, and the array will store the values themselves.

Algorithm Steps

Insert: Add the value to the end of the array and store its index in the hash map.
Remove: To remove an element in O(1), we swap it with the last element in the array, update the hash map for the swapped element, and then pop from the array.
GetRandom: Simply pick a random index from the array.

Map (Value → Index)

List

Perform an operation.

Insert Delete GetRandom O(1) Solution


import random

class RandomizedSet:
    def __init__(self):
        self.numMap = {}
        self.numList = []

    def insert(self, val: int) -> bool:
        res = val not in self.numMap
        if res:
            self.numMap[val] = len(self.numList)
            self.numList.append(val)
        return res

    def remove(self, val: int) -> bool:
        res = val in self.numMap
        if res:
            idx = self.numMap[val]
            lastVal = self.numList[-1]
            self.numList[idx] = lastVal
            self.numList.pop()
            self.numMap[lastVal] = idx
            del self.numMap[val]
        return res

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