Leetcode 380: Insert Delete Getrandom O(1)
I Came Across This Leetcode Problem Insert Delete Getrandom Where It Is Asked to Implement a Data Structure to Support Insert, Delete and getRandom in Average...
I came across this leetcode problem Insert Delete GetRandom where it is asked to implement a Data Structure to support Insert, Delete and getRandom in average O(1) time, and solved it as using map and a vector. My solution passes all the test cases except for the last one and I'm not able to figure out why? The last test case is really very large to debug.
I changed my code a little bit and then it passes but still didn't got why the previous one didn't pass.
Non-Accepted Solution:
class RandomizedSet {
map<int, int> mp;
vector<int> v;
public:
/** Initialize your data structure here. */
RandomizedSet() {
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool insert(int val) {
if(mp.find(val) == mp.end()){
v.push_back(val);
mp[val] = v.size()-1;
return true;
}
else return false;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
if(mp.find(val) == mp.end()){
return false;
}
else{
int idx = mp[val];
mp.erase(val);
swap(v[idx], v[v.size()-1]);
v.pop_back();
if(mp.size()!=0) mp[v[idx]] = idx;
return true;
}
}
/** Get a random element from the set. */
int getRandom() {
if(v.size() == 0) return 0;
int rndm = rand()%v.size();
return v[rndm];
}
};
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/
Accpeted Solution: The problem is in remove function, when i change the remove function by below code, it passes.
if(mp.find(val) == mp.end()){
return false;
}
else{
int idx = mp[val];
swap(v[idx], v[v.size()-1]);
v.pop_back();
mp[v[idx]] = idx;
mp.erase(val);
return true;
}
I don't understand why is this happening. I placed the mp.erase(val) in the last and replaced the if(mp.size()!=0) mp[v[idx]] = idx to mp[v[idx]] = idx only.
Both versions of remove function are able to handle corner case - when there is only single element left in the map and we want to remove it.
1 Answer
This is because of undefined behavior when the element removed is the last element.
e.g, say the operations are
insert(1) // v = [1], mp = [1->0]
insert(2) // v = [1,2], mp = [1->0, 2->1]
remove(2):
int idx = mp[val]; // val = 2, idx = 1
mp.erase(val); // mp = [1->0]
swap(v[idx], v[v.size()-1]); // idx = v.size()-1 = 1, so this does nothing.
v.pop_back(); // v = [1]
if(mp.size()!=0) mp[v[idx]] = idx; // mp[v[1]] = 1.
// But v[1] is undefined after pop_back(), since v's size is 1 at this point.
I am guessing that it doesn't clear the memory location accessed by v[1], so v[1] still points to 2, and it ends up putting 2 back into mp.
James Sterling reports on renewable energy developments, climate policy, ecological conservation, and green tech innovations around the globe.
