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

  • 0

    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;
        /** 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;
            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.insert(make_pair(data.back(), loc));
            swap(data[loc], data[data.size() - 1]);
            return true;
        /** Get a random element from the collection. */
        int getRandom() {
            return data[rand() % data.size()];

  • 0

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

Log in to reply

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