380.Insert Delete GetRandom O(1)

Tags: [implementation], [array], [map], [data_structure]

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

Design a data structure that supports all following operations in average O(1) time.

1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

Solution: Map

class RandomizedSet(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.elem_to_index_map = {}
        self.index_to_elem_map = {}
        self.counter = 0

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.elem_to_index_map:
            return False

        self.counter += 1
        self.elem_to_index_map[val] = self.counter - 1
        self.index_to_elem_map[self.counter - 1] = val
        return True

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.elem_to_index_map:
            return False

        removed_index = self.elem_to_index_map.pop(val)
        del self.index_to_elem_map[removed_index]

        if removed_index != self.counter - 1:
            last_elem_index = self.counter - 1
            last_elem = self.index_to_elem_map[last_elem_index]
            self.elem_to_index_map[last_elem] = removed_index
            self.index_to_elem_map[removed_index] = last_elem

        self.counter -= 1
        return True

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        if not self.counter:
            return None

        random_index = random.randint(0, self.counter - 1)
        return self.index_to_elem_map[random_index]

# 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()

Revelation:

• Maintain the 'index__to__elem_map'. When we generate the random index, we can use this map to retrieve the element based on the index

Note:

• Time complexity: If we assume the 'get' and 'remove' operation in hash map is O(1), all these three operations 'insert', 'remove', and 'getRandom' time complexity are O(1).
• If the current removed element has already been the 'last' element, we don't need to update the maps for the last element (because it has been removed).

Solution: Array, Map

class RandomizedSet(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.arr = []
        self.elem_to_index_map = {}

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.elem_to_index_map:
            return False

        self.arr.append(val)
        self.elem_to_index_map[val] = len(self.arr) - 1
        return True

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if val not in self.elem_to_index_map:
            return False

        removed_elem_index = self.elem_to_index_map.pop(val)
        if removed_elem_index == len(self.arr) - 1:
            self.arr.pop()
            return True

        self.arr[removed_elem_index], self.arr[-1] = self.arr[-1], self.arr[removed_elem_index]
        self.arr.pop()
        self.elem_to_index_map[self.arr[removed_elem_index]] = removed_elem_index
        return True

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        if not self.arr:
            return None

        random_index = random.randint(0, len(self.arr) - 1)
        return self.arr[random_index]

# 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()

Revelation:

• If the element which will be removed is the last element of the array, we just need to remove it directly, do not need update the do the swapping and updating the map.
• The Python list.append operation's time complexity is amortized O(1), not O(1). Reference: http://stackoverflow.com/questions/33044883/why-is-the-time-complexity-of-pythons-list-append-method-o1