LeetCode 380: Insert Delete GetRandom O(1)

If we have a set of values: $\{ 1, 2, 3 \}$ , in a sequence of getRandom() calls, each of the six permutations of $\langle 1, 2, 3 \rangle$ must appear roughly equal number of times. We assume random.randint(lo, hi) takes $\mathcal{O}(1)$ time.

List

We can keep a list of values and pick an index at random.

Say there are $n$ values. Total space is $\mathcal{O}(n)$ .

class RandomizedSet:

    def __init__(self):
        self.values = []

    def insert(self, val: int) -> bool:
        if val in self.values:
            return False
        
        self.values.append(val)

    def remove(self, val: int) -> bool:
        if val not in self.values:
            return False
        
        i = self.values.index(val)
        self.values.pop(i)
        return True

    def getRandom(self) -> int:
        i = random.randint(0, len(self.values)-1)
        return self.values[i]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

List and set

class RandomizedSet:

    def __init__(self):
        self.values = []
        self.value_set = set()

    def insert(self, val: int) -> bool:
        if val in self.value_set:
            return False

        self.values.append(val)
        self.value_set.add(val)

    def remove(self, val: int) -> bool:
        if val not in self.value_set:
            return False
        
        i = self.values.index(val)
        self.values.pop(i)
        self.value_set.remove(val)

        return True

    def getRandom(self) -> int:
        i = random.randint(0, len(self.values)-1)
        return self.values[i]


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

List and dict

To find the index of the to-be-removed value, we keep a map: {val -> index}. Deleting an index in the middle of the list messes up indices to the right. So, we swap the to-be-deleted index with the last index and pop the last and delete from the map. We also update the swapped in value in the {val -> index} map. Even if there is a single value, this works.

Say there are $n$ values. Total space is $\mathcal{O}(n)$ .

class RandomizedSet:
 
    def __init__(self):
        self.values = []
        self.value_map = {}
 
    def insert(self, val: int) -> bool:
        if val in self.value_map:
            return False
 
        self.value_map[val] = len(self.values)
        self.values.append(val)
 
    def remove(self, val: int) -> bool:
        if val not in self.value_map:
            return False
         
        i = self.value_map[val]
        self.values[i], self.values[-1] = self.values[-1], self.values[i]
        self.value_map[ self.values[i] ] = i
        self.values.pop()
        del self.value_map[val]
 
        return True
 
    def getRandom(self) -> int:
        i = random.randint(0, len(self.values)-1)
        return self.values[i]
 
 
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

Instead of randint() we can also use choice().

class RandomizedSet:
 
    def __init__(self):
        self.values = []
        self.value_map = {}
 
    def insert(self, val: int) -> bool:
        if val in self.value_map:
            return False
 
        self.value_map[val] = len(self.values)
        self.values.append(val)
 
    def remove(self, val: int) -> bool:
        if val not in self.value_map:
            return False
         
        i = self.value_map[val]
        self.values[i], self.values[-1] = self.values[-1], self.values[i]
        self.value_map[ self.values[i] ] = i
        self.values.pop()
        del self.value_map[val]
 
        return True
 
    def getRandom(self) -> int:
        return choice(self.values)
 
 
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

unreasonably effective