Insert Delete GetRandom O(1)

When it comes to designing data structures, one often seeks optimal solutions that offer efficient operations. In this article, we will explore the approach to tackling this problem using JavaScript.

Problem Statement:

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.

---

Approach:

For this problem, we need to make insert, remove, and getRandom all to O(1) time complexity, so it's straightforward to think about using a map. With a map, we could implement the insert and remove easily with O(1) time complexity. But how about getRandom?

Let’s take a look at what operations do we need for the getRandom method:

• Get a random number.

• Get the real value according to that random number.

Looks like it’s pretty easy, right? We could get a random number by Math.random, and use an array to store index-based values.

But when we try to finish the code, we may find the remove method could not be easy, since if we use something like splice to remove the value in an array, it could be not O(1) depends on the implementation, and all the indexes after this element need to be updated.

So, here comes the final key point for this problem, how do we make it O(1) with steady indexes? Let’s list some clues:

• If we want steady indexes, then we can’t remove this element from the list. We must put a value here.

• If we wanna remove a value with O(1) in a list, it’s straightforward to think about removing the last value.

Combined with these clues, it is not difficult for us to find out that we could swap the target value and the last value, then remove it. This could meet our two needs at the same time.

At this moment, the whole strategy is clear, so the next step is just coding:

// ES6 Arrow Function
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 idx = this.map.get(val);
    this._swap(idx, this.list.length - 1);
    this.list.pop();
    this.map.set(this.list[idx], idx);
    this.map.delete(val);
    return true;
  }

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

  _swap(a, b) {
    const tmp = this.list[a];
    this.list[a] = this.list[b];
    this.list[b] = tmp;
  }
}

Time Complexity:

• Insertion: O(1)

• Deletion: O(1)

• Get Random: O(1)

Space Complexity: O(N)

N is the number of elements stored in the data structure. The array this.list stores the elements, and the hash map this.map stores the mapping of elements to their indices.

---

Note: The credit for this solution goes to PoppinL. Her detailed answer on leetcode helped me understand this problem better.

I hope this article has provided you with valuable insights and helped you better understand the approach to solve this problem. Happy coding!

Problem - Leetcode 380