medium

Insert Delete GetRandom O(1)

To implement the RandomizedSet class in JavaScript with average O(1) time complexity for each operation, we can use a combination of an array and an object. The array will store the elements in the set, while the object will map each element to its corresponding index in the array. This allows us to achieve constant time complexity for insert and remove operations, as well as getRandom.

Here's the implementation:

var RandomizedSet = function () {
  this.set = []; // Array to store the elements
  this.indexMap = {}; // Object to map element to its index
};
 
RandomizedSet.prototype.insert = function (val) {
  if (this.indexMap[val] !== undefined) {
    return false; // Element already exists in the set
  }
 
  this.set.push(val); // Add element to the end of the array
  this.indexMap[val] = this.set.length - 1; // Map element to its index
  return true;
};
 
RandomizedSet.prototype.remove = function (val) {
  if (this.indexMap[val] === undefined) {
    return false; // Element doesn't exist in the set
  }
 
  const lastIndex = this.set.length - 1;
  const index = this.indexMap[val]; // Get the index of the element to be removed
  const lastElement = this.set[lastIndex];
 
  // Swap the element to be removed with the last element in the array
  this.set[index] = lastElement;
  this.indexMap[lastElement] = index;
 
  // Remove the element from the array and index map
  this.set.pop();
  delete this.indexMap[val];
 
  return true;
};
 
RandomizedSet.prototype.getRandom = function () {
  const randomIndex = Math.floor(Math.random() * this.set.length);
  return this.set[randomIndex];
};

Time Complexity:

• The insert operation has an average time complexity of O(1) because both array push and object assignment are constant time operations.
• The remove operation has an average time complexity of O(1) because it involves swapping elements and updating the index map, which are constant time operations.
• The getRandom operation has a time complexity of O(1) since we are generating a random index and accessing the element directly from the array.

Space Complexity:

• The space complexity is O(N), where N is the number of elements in the set. We are using an array to store the elements, which requires O(N) space. Additionally, we have an object (indexMap) that stores the mapping of elements to their indices, which also requires O(N) space in the worst case.