# C++ AC Solution with unordered_map and vector (104ms)

• The main idea is use unordered_map<int, vector<int>> to record multiple location of numbers, and use vector<int> to store all numbers. The main different with problem Insert Delete GetRandom O(1) is :

1. [insert] We should always push number, no matter the number is existing or not.
2. [delete] We can erase the number from hashmap only when all the number are removed. (we can get this info by checking the length hashmap[val])

Besides, the if statement in delete() can reduce redundant access to unordered_map and vector, which can slightly improve its performance.

If you have any suggestion, please leave the comment. Thanks. :)

``````class RandomizedCollection {
public:
/** Initialize your data structure here. */
RandomizedCollection() {}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
bool insert(int val) {
nums.push_back(val);
m[val].push_back(nums.size() - 1);
return m[val].size() == 1;
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
if(m.find(val) == m.end())  return false;
int last = nums.back();
if(val != last) {   // Reduce redundant access.
nums[m[val].back()] = last;
m[last].back() = m[val].back();
}
m[val].pop_back();
nums.pop_back();
if(m[val].size() == 0)
m.erase(val);
return true;
}

/** Get a random element from the collection. */
int getRandom() {
return nums[rand() % nums.size()];
}

private:
unordered_map<int, vector<int>> m;
vector<int> nums;
};
``````

• Hi, I have a little question. If the number is insert like this: ......5......4, 4. If you wanna delete 5, then the array will be ......4......4, 5 first, and you delete 5 from the end, which makes the array to ......4......4. But in the map, the last index of 4 would become the index of the first 4 instead of the second 4. This time, when you want to delete something, you will exchange the index of first 4 and the deleted element, this will make the whole vector after the first 4 move 1 step forward. Basically, this makes the operation not O(1). I'm not familiar with C++, don't know if the vector will work this way. Thanks.

• @fightingagain The default behavior of my implementation is to use last number to overwrite the target number by `nums[m[val].back()] = last;`and then pop_back() the number vector. For the hashmap, I will update the new location of last number by `m[last].back() = m[val].back();` and pop_back() the useless location, which means I will only use the later location of last number. (in your case, I will update the index of latter 4, rather than the first one.)

• I prefer to use a vector instead of a set to implement this question, but this part is exactly where I don't understand when I'm writing my code. I'll draw the map:
......5......4, 4
Initially the map would look like this:
5 -> [3]
4 -> [10, 11]
When deleting 5:
......4......4, 4 -> I got this from your if block: m[val].back = 3, last = 4.
Then the map would be:
4 -> [10, 3]
5 -> [3] -> m[4].back() should be 11 first, then you update it to m[val].back() which is 3.
Then, you delete m[5].back() which is 3, which makes the map:
4 -> [10, 3]
So at this moment, the last index of 4 would be 3, instead of 10.

Thanks.

• This case fails:

["RandomizedCollection","insert","insert","insert","insert","insert","insert","remove","remove","remove","remove","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom","getRandom"]
[[],[10],[10],[20],[20],[30],[30],[10],[10],[30],[30],[],[],[],[],[],[],[],[],[],[]]

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.