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

LeetCode 380

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.