# C++ 79ms solution using map and set with explanation

• Inspired by the question with no duplicate allowed.

An example of running the code:

1. "insert 1, insert 2, insert 1, insert 3":
m: 1 => {0, 2}, 2 => {1}, 3 => {3}
v: [1, 2, 1, 3]
2. "remove 2"
m: 1 => {0, 2}, 3 => {1}
v: [1, 3, 1]
3. "remove 1"
m: 1 => {0}, 3 => {1} (for key '1', it's 1 => {2}, then 1 => {}, and finally 1 => {0})
v: [1, 3] (it's [1(1), 3, 1(2)] -> [1(2), 3, 1(2)] -> [1(2), 3], where 1(1) and 1(2) means first and second 1's in the previous vector [1, 3, 1])
``````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) {
bool ne = (m.find(val) == m.end());
v.push_back(val);
m[val].insert(v.size()-1); // Insert the index of this number to the map
return ne;
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
bool found = (m.find(val) != m.end());
if (!found) return false;
int ind = *(m[val].begin()); // The number val has one or more copies in v; get the index of first copy
m[val].erase(m[val].begin()); // Remove ind from the set
if (ind < v.size()-1) { // If ind is not last in v
v[ind] = v.back(); // We want to keep the number at back but remove the number at ind
// The below two steps update the index of back number from back to ind
m[v.back()].erase(v.size()-1);
m[v.back()].insert(ind);
}
v.pop_back(); // Remove the duplicated back number
if (m[val].empty()) m.erase(val); // If val has an empty set, all its copies have been removed from v. Delete it for consistency
return found;
}

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

private:
/** key: number inserted */
/** val: a set of indices where key resides in v */
unordered_map<int, unordered_set<int>> m;
/** stores number inserted; the indices are stored in m */
vector<int> v;
};
``````

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