Solution to LeetCode Problem 380. Insert Delete GetRandom O(1) in JavaScript

  

A solution to LeetCode Problem 380. Insert Delete GetRandom O(1) in JavaScript 

If you're preparing for technical interviews or want to improve your coding skills, solving practice problems on LeetCode is a great way. 

In this post, we'll discuss a solution to the "380. Insert Delete GetRandom O(1)" problem on LeetCode.

Implement the RandomizedSet class:

• RandomizedSet() Initializes the RandomizedSet object.
• bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
• bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
• int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

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

 

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

 

Constraints:

• -231 <= val <= 231 - 1
• At most 2 * 105 calls will be made to insert, remove, and getRandom.
• There will be at least one element in the data structure when getRandom is called.
  
  
  

Solution

We can use a combination of a JavaScript Map object and an array to implement this data structure. The Map object will allow us to store the values and their indices in the array, and the array will allow us to easily implement the getRandom() function.

To implement the insert() function, we can simply add the value to the end of the array and store its index in the Map object. If the value already exists in the Map, we can return false.

To implement the remove() function, we can remove the value from the Map and swap it with the last element in the array. This will allow us to maintain the O(1) time complexity for both insert and remove.

To implement the getRandom() function, we can simply return a random element from the array using the Math.random() function.

Here is the code for the RandomizedSet class:

class RandomizedSet {
  constructor() {
    this.map = new Map();
    this.list = [];
  }

  insert(val) {
    if (this.map.has(val)) return false;
    this.map.set(val, this.list.length);
    this.list.push(val);
    return true;
  }

  remove(val) {
    if (!this.map.has(val)) return false;
    const index = this.map.get(val);
    this.map.delete(val);
    if (index < this.list.length - 1) {
      // If the element is not the last element, move the last element to its place
      const last = this.list[this.list.length - 1];
      this.list[index] = last;
      this.map.set(last, index);
    }
    this.list.pop();
    return true;
  }

  getRandom() {
    return this.list[Math.floor(Math.random() * this.list.length)];
  }
}

The time complexity of the updated solution is still O(1) for all three operations: insert, remove, and getRandom().

The insert() operation has a time complexity of O(1), because it simply adds a new element to the end of the array and sets a value in the map. Both of these operations have constant time complexity.

The remove() operation has a time complexity of O(1) in the worst case, because it involves deleting a value from the map and replacing an element in the array with the last element in the array. Both of these operations have constant time complexity. In the worst case, the element being removed is not the last element in the array, so the remove operation also involves updating the map and the value of the last element in the array. However, these operations also have constant time complexity, so the overall time complexity of the remove operation remains O(1).

The getRandom() operation has a time complexity of O(1), because it involves generating a random number within the range of the array's indices and then accessing an element at that index. Both of these operations have constant time complexity.

Overall, the updated solution has a time complexity of O(1) for all three operations, which means that the time taken to perform these operations does not depend on the size of the input.

I hope this helps! Let me know if you have any questions or suggestions for improvement.