This is related to the leetcode - question here, which asks:
Implement the RandomizedSet class:
You must implement the functions of the class such that each function works in average O(1) time complexity.
I am able to pass some of the test cases but it fails one of the test cases (where in some places, my program returns undefined
). What is it that I am doing wrong here? I am unable to find my mistake.
var RandomizedSet = function() {
this.map = new Map();
this.vector = [];
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.insert = function(val) {
if(this.map.has(val)) return false;
else {
let position = 0;
if(this.vector.length > 0)
position = this.vector.length-1;
this.map.set(val, position);
this.vector.push(val);
return true;
}
};
/**
* @param {number} val
* @return {boolean}
*/
RandomizedSet.prototype.remove = function(val) {
if(this.map.has(val)) {
const index = this.map.get(val);
const lastVal = this.vector[this.vector.length-1];
this.vector[index] = lastVal;
this.vector.pop();
this.map.delete(val);
return true;
}else {
return false;
}
};
/**
* @return {number}
*/
RandomizedSet.prototype.getRandom = function() {
const randIndex = Math.floor(Math.random() * this.vector.length);
return this.vector[randIndex];
};
/**
* 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()
*/
When moving the last element into the place of the removed element, you forgot to update the moved element's index in the map:
RandomizedSet.prototype.remove = function(val) {
if(this.map.has(val)) {
const index = this.map.get(val);
const lastVal = this.vector[this.vector.length-1];
this.vector[index] = lastVal;
this.vector.pop();
this.map.set(lastVal, index); // ADDED
this.map.delete(val);
return true;
}else {
return false;
}
};
Be aware of the case index == this.vector.length-1
; the order of operations shown above will handle this case correctly without additional code.