380. Insert Delete GetRandom O(1)

Insert Delete GetRandom

Problem Description

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 on 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.

Approach) Array + Map

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 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.

var RandomizedSet = function() {
    this.map = new Map();
    this.list = [];
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.insert = function(val) {
    if (this.map.has(val)) return false;

    this.map.set(val, this.list.length);
    this.list.push(val);
    return true;
};

/** 
 * @param {number} val
 * @return {boolean}
 */
RandomizedSet.prototype.remove = function(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;
};

/**
 * @return {number}
 */
RandomizedSet.prototype.getRandom = function() {
    return this.list[Math.floor(Math.random() * this.list.length)];
};

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


/** 
 * 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) Another way with Array + Map

class RandomizedSet {
    
    constructor() {
        this.map = new Map();
        this.arr = [];
    }
    
    insert(val) {
        if(this.map.has(val)) return false;
        
        this.map.set(val, this.arr.length);
        this.arr.push(val);
        return true;
    }
    
    remove(val) {
        if(!this.map.has(val)) return false;
        
        const valIdx = this.map.get(val);
        const lastIdx = this.arr.length-1;
        const lastNum = this.arr[lastIdx];
        
        // swap 'val' with the last element
        [this.arr[valIdx], this.arr[lastIdx]] = [this.arr[lastIdx], this.arr[valIdx]];
        // pop 'val' from the array
        this.arr.pop();
        // update the last element's index to be 'val's' index
        this.map.set(lastNum, valIdx);
        // delete 'val' from the map
        this.map.delete(val);
        return true;
    }
    
    getRandom() {
        const randIdx = Math.floor(Math.random() * this.arr.length);
        return this.arr[randIdx];
    }
}

Conclusion

That’s all folks! In this post, we solved LeetCode problem 380. Insert Delete GetRandom O(1)

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!