#380. Insert Delete GetRandom O(1)

https://leetcode.com/problems/insert-delete-getrandom-o1/?envType=daily-question&envId=2024-01-15

var RandomizedSet = function () {
    this.store = []
    this.storeMap = new Map()
};

RandomizedSet.prototype.insert = function (val) {
    if (this.storeMap.has(val)) return false

    this.store.push(val)
    this.storeMap.set(val, this.store.length - 1)
    return true
};

RandomizedSet.prototype.remove = function (val) {
    if (! this.storeMap.has(val)) return false

    let lastItem = this.store[this.store.length - 1]
    let valIndex = this.storeMap.get(val)
    //in map
    //val is key and index is value

    this.store[valIndex] = lastItem
    //swap the last item with val to be removed
    //this creates a duplicate
    this.storeMap.set(lastItem, valIndex)
    //we give the lastItem the index of the val to be removed

    this.store.pop()
    //remove the duplicate at the last index
    this.storeMap.delete(val)

    return true
};

RandomizedSet.prototype.getRandom = function () {
    let random = Math.floor(Math.random() * this.store.length)
    return this.store[random]

};

This seems straight forward initially but it isn't really. The remove method is quite tricky.

We swap the element to be removed with the last element in the array after getting it's index from the storeMap, then pop the array to maintain 0(1) removal. But the storeMap has to be updated properly for future class actions to work properly.

To do that, we store the last item which is now in a position other than the last position in the map with the index of the value to be removed into the storeMap, then the value to be removed and it's index is removed from the storeMap.