Insert Delete GetRandom O(1) - LeetCode

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.

Algorithm:

The intuition here is whenever you want to achieve in less time, you have to sacrifice space. So we are gonna use extra space with hash table.

/**
 * Initialize your data structure here.
 */
var RandomizedSet = function () {
  this.nums = new Array();
  this.locs = new Object();
};

/**
 * 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 (!(val in this.locs)) {
    this.nums.push(val);
    this.locs[val] = this.nums.length - 1;
    return true;
  }
  return false;
};

/**
 * 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(val in this.locs) {
        let loc = this.locs[val];
        let lastEl = this.nums[this.nums.length - 1];
        this.nums[loc] = lastEl;
        this.locs[lastEl] = loc;
        this.nums.pop();
        delete this.locs[val];
        return true;
    }
    return false;
};

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