# C++ 52ms beating 89% solutions, Real O(1), correct use of unordered_multimap

• I saw there are several top rated solutions using unordered_map, but in this case unordered_multimap is more efficient. While there's one existing solution using unordered_multimap, it has a major bug - it didn't check to make sure that we changed the correct entry inside the map inside the remove method. The below code uses the equal_range to make sure we delete the correct entry. It runs in 52ms and beats 89% of the solutions.

``````class RandomizedCollection {
vector<int> data;
unordered_multimap<int, int> mp;
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 res = true;
if (mp.find(val) != mp.end()) res = false;
data.push_back(val);
mp.insert(make_pair(val, data.size() - 1));
return res;
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool remove(int val) {
auto it = mp.find(val);
if (it == mp.end()) return false;
int loc = it->second;
auto ir = mp.equal_range(data.back());
for (auto irt = ir.first; irt != ir.second; ++irt) {
if (irt->second == data.size() - 1) {
mp.erase(irt);
break;
}
}
mp.insert(make_pair(data.back(), loc));
swap(data[loc], data[data.size() - 1]);
data.pop_back();
mp.erase(it);
return true;
}

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

• The remove function here isn't O(1)?

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