How to Solve Insert Delete getRandom O(1)

Insert Delete getRandom O(1) Introduction

The Insert Delete getRandom O(1) problem involves implementing a class that enables the insertion, deletion, and retrieval of a random element in constant time. Solving this design task requires a strong understanding of the operational time complexities for arrays and hash maps.

Insert Delete getRandom O(1) Problem

Design and implement an efficient sampler that can handle the following operations in constant time:

• RandomizedSet() initializes the RandomizedSet object.
• insert(string val) Inserts an item val into the set if not already present; returns true if the item was not present, false otherwise.
• remove(string val) Removes an item val from the set if present; returns true if the item was present, false otherwise.
• getRandom() Returns a random element from the current set of elements.

Implement the functions of the class such that each function works in average O(1) time complexity.

Example Inputs and Outputs

Example 1

Input: ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]

[[], ["a"], ["b"], ["b"], [], ["a"], ["b"], []]

Output: [null, true, false, true, 'b', true, false, 'b']

Explanation:

• RandomizedSet: initialize the object
• insert('a'): inserts a into the set. Returns true as it is inserted successfully.
• remove('b'): removes b from the set. Returns false as it does not exist in the set.
• insert('b'): inserts b into the set. Returns true as it is inserted successfully.
• getRandom(): returns either a or b randomly.
• remove('a'): removes a from the set. Returns true as it is removed successfully.
• insert('b'): inserts b into the set. Returns false as it already exists in the set.
• getRandom(): returns b as it is the only item in the set.

Constraints

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

Insert Delete getRandom O(1) Solutions

When writing code to store data we have lots of data structures to choose from: arrays / lists, trees, graphs, hashmaps, linked lists, sets, etc. And different data structures have different time complexities for various operations, so depending on what we are trying to achieve, the “right” data structure to use will change. In this problem, we need to achieve O(1) for insert, remove and getRandom. Because of this requirement, let’s focus on two widely used data structures that have certain O(1) operations: hashmaps and arrays.

• Hashmap
  • add a key: O(1)
  • read a given key: O(1)
  • delete a given key: O(1)
  • read a random key: O(N)
    • get all the keys in the hashmap: O(N)
    • get a random key from the keys: O(1)
• Array
  • add an item to the end of the array: O(1)
  • read the value without providing an index: O(N)
  • delete an item from the end of the array: O(1)
  • delete an item from the middle of the array: O(N)
    • need to create a new array and copy all the items from the old array (except the item to be deleted) into the new array: O(N)
  • get a random item: O(1)
    • get a random index within the range of the array length: O(1)
    • read the value for the random index: O(1)

Back to our problem at hand, based on the time complexities above we can use a hashmap to achieve O(1) inserts and deletes, but a hashmap alone will not be sufficient for getting a random element. Likewise, we can use an array to get a random element but cannot use an array alone for O(1) reads and deletes. Since there is no limitation on space usage, we can combine both data structures in our implementation:

1. Use a hashmap to memorize the positions for all the items in the array to achieve O(1) read and delete.
2. Use an array to get a random element with O(1).

Approach 1: Hashmap + Array

For add operations, we can:

• Check if the string exists in the hash map or not; return false if we already have the string.
• Append the string to the end of the array. The index of the newly-added string will be array_length - 1.
• Add the string into the hashmap with the key as the string itself, and the value as the index.

For delete operations, we can:

• Get the index of the string to be deleted from the hashmap.
• We can then swap the string to be deleted with the last element in the array.
• Next, we need to update the keys in the hashmap with their new array index values.
• Lastly, we pop the last element from the array and delete the key from the hashmap.

For getRandom operations, we can:

• Get the length of the array, knowing the last index of the array is array_length - 1.
• Generate a random number (randomIdx) in the range between 0 (the first index) and the last index (inclusive).
• Return the element stored at the random index in the array.

Insert Delete getRandom O(1) Python Solution - Hashmap + Array

from random import randint

class RandomizedSet(object):

def __init__(self):
        # Key is the string, value is the index of the string inside the array
        # Use this hashmap to keep track of the position of the string in the array
        self.item_to_index = {}

# The array of strings we have inserted
        self.item_arr = []

def insert(self, item):
        # Only insert if the string does not already exist
        if item in self.item_to_index:
            return False

# Append this new string to the end of the array
        index = len(self.item_arr)
        self.item_to_index[item] = index
        self.item_arr.append(item)

return True

def remove(self, item):
        # Only remove if the string exists
        if item not in self.item_to_index:
            return False

# Swap the string to be removed to the end of the array
        index = self.item_to_index[item]
        last_item = self.item_arr[-1]
        self.item_to_index[last_item] = index
        self.item_arr[index] = last_item
        self.item_arr.pop()
        del self.item_to_index[item]

return True

def getRandom(self):
        # Randomly pick an index available
        index = randint(0, len(self.item_arr) - 1)
        return self.item_arr[index]

Time/Space Complexity

• Time complexity: O(1) for all the operations.

• Space complexity: O(N)

  • The hashmap takes O(N)
  • The array list takes O(N)