Constant Time Insertion, Deletion, and Retrieval of Random Elements#

Design a data structure that supports the following operations in average time complexity O(1):

• insert(val): Inserts the element val into the collection if it does not already exist.
• remove(val): Removes the element val from the collection if it exists.
• getRandom: Returns a random element from the existing collection, with each element having an equal probability of being returned.

Example#

Solution#

/**
 * Initialize your data structure here.
 */
var RandomizedSet = function() {
    this.hashTable = {};
    this.arr = [];
};

/**
 * Inserts a value to the set. Returns true if the set did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if(this.hashTable[val] !== undefined) return false;
    this.hashTable[val] = this.arr.length;
    this.arr.push(val);
    return true;
};

/**
 * Removes a value from the set. Returns true if the set contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(val) {
    if(this.hashTable[val] === undefined) return false;
    var index = this.hashTable[val];
    var key = this.arr[this.arr.length-1];
    this.hashTable[key] = index;
    delete this.hashTable[val];
    this.arr[index] = key;
    this.arr.pop();
    return true;
};

/**
 * Get a random element from the set.
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    return this.arr[~~(Math.random() * this.arr.length)];
};

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

Approach#

The problem requires implementing a data structure where insertion and deletion operations have a time complexity of O(1). It is easy to think of linked lists and hash tables. However, the problem also requires the time complexity for returning a random value to be O(1). Simple linked lists and hash tables cannot satisfy this requirement. Additionally, the time complexity of finding a value in a linked list given a specific value is O(n), which is not suitable for this problem. Therefore, to meet these requirements, we need to use a hash table in combination with an array. In this approach, the value serves as the key in the hash table, and the index in the array serves as the value in the hash table. This ensures that the time complexity for insert and getRandom operations is O(1. For the remove operation, the given value's index in the array is retrieved, and then the last value in the array is overwritten onto this index. Subsequently, the index of the last value in the hash table is updated, and finally, the last value in the array and the key representing the given value in the hash table are deleted. This implementation achieves an O(1) time complexity for the remove operation.

To begin, the constructor defines the object as the hash table and the array. In the insert operation, if the value already exists in the hash table, it directly returns false; otherwise, the value is added to the hash table as a key, and the length of the array serves as the value. The value is then appended to the array, and true is returned. In the remove operation, it first checks if the value does not exist and directly returns false. If the value exists, it retrieves the index of the value and then retrieves the last value from the array. Subsequently, in the hash table, the key for this last value is replaced with the index, effectively overwriting the value to be deleted with the last value. Next, it deletes the index of the value to be removed from the hash table, replaces the value at the given index in the array with the last value, deletes the last value from the array, and finally, returns a random value from the array in the getRandom operation.

Daily Challenge#

Reference#