C++ solution using map and vector with detailed explanation


  • 4
    C

    It is obvious that we should use hash map to achieve O(1) insert and remove.
    But how to achieve O(1) getRandom() remains a problem.
    Here is what I think:
    we use vector arr to store all the elements in this collection, so that

    arr[rand()%arr.size()]
    

    will help to realize getRandom() in O(1).
    Every time we want to remove an element, we swap this element with the last element in arr and then pop back the last element.

    And in hash map, the element value is the key, and its index in the arr is the value.
    Every time we remove an element A, we should remove A both from map and arr.

    class RandomizedCollection {
    private:
        map<int, vector<int>> dic;
        vector<int> arr;
        
    public:
        RandomizedCollection() {
        }
    
        bool insert(int val) {
            arr.push_back(val);//add val in arr
            dic[val].push_back(arr.size() - 1);//add its index in dic[val]
            return dic[val].size() == 1;
        }
        
        bool remove(int val) {
            if(dic[val].size() == 0)
            {
                return false;
            }
            int idx = dic[val].back();//arr[idx] = val
            dic[val].pop_back();
           //swap arr[idx] and arr[arr.size()-1] if idx != arr.size()-1
           //modify the dic at the same time.
            if(arr.size() - 1 != idx);
            {
                int tmp = arr.back();
                arr[idx] = tmp;
         //the new index of tmp is now idx, so modify the dic accordingly.
                dic[tmp].pop_back();
                dic[tmp].push_back(idx);
            }
           //remove the last element in arr
            arr.pop_back();
            return true;
        }
    
        int getRandom() {
            return arr[rand()%arr.size()];
        }
    };
    

    Comments are welcomed!


  • 7

    @ccpromise Nice try with unordered_map<int, vector<int>>, but I think it will fail in some cases. For example, arr = [1,1,2,1,2,2], and you try to remove(1). For "1", the vector stored in hashmap is [0,1,3] and the vector for "2" is [2,4,5]. After your remove(1), the vector for "1" is [0,1], but the vector for "2" is [2,4,3]. Next, if you call remove(2), then the vector for "2" is [2,4] but arr.pop_back() actually pop the index 4 for "2" out. Please correct me if I was wrong...


  • 2

    @haruhiku Actually I've just added a similar test case based on yours, and ironically your solution fails the test case. Thanks for your test case and hope it is helpful!


  • 1
    C

    @haruhiku
    Hi haruhiku,
    Thanks for pointing it out. Actually, I find dic does not always contain the valid index. However, I find it still works.
    In your case, arr = [1,1,2,1,2,2]. remove(1), and dic[1]=[0,1], dic[2]=[2,4,3]. If we remove(2), dic[2] will pop out idx=3. Since idx=3 is not the last index in arr. Then tmp=2, dic[tmp] will pop out index 4 and push idx=3. So remove(2), dic[1]=[0,1], dic[2]=[2,3]. If we do not remove(2) but remove(1), dic[1]=[0], dic[2]=[2,4,1]. In this case, 4 is not a valid index.
    However it does not matter. I find that we only need to make sure 1)the last index in dic[val] is valid so that remove(val) can work correctly, and 2)the arr always contains the correct number of values(this is more obvious) so that getRandom() can work correctly.
    In this example, if we continue to remove(2), dic[1]=[0],dic[2]=[2,1]. Remove(2) again, dic[1]=[0], dic[2]=[1]. You see it still works.

    The proof of the first condition remains a problem. I need some time to think about it.

    Thanks for pointing out. Your comments help^^


  • 0

    @ccpromise
    Hi ccpromise. Ok, got it with your explanation. :)

    I was just not sure if there was a chance that you stored the wrong index and tried to access the corresponding element with arr[idx] = tmp (out of bound or sth). Now I think it works fine.

    But I find a very tiny mistake in your code when I run it. In your remove(), you have a ";" in "if(arr.size() - 1 != idx);". Hope it helps.


  • 0
    J

    The code is having runtime error, but I can't find the problem...


  • 2
    Y

    This following part may have issues:

    dic[tmp].pop_back();
    dic[tmp].push_back(idx);
    

    We cannot always use idx to replace the last item in the vector.


  • 3
    W

    @yicui said in C++ solution using map and vector with detailed explanation:

    This following part may have issues:

    dic[tmp].pop_back();
    dic[tmp].push_back(idx);
    

    We cannot always use idx to replace the last item in the vector.

    Exactly. The solution is wrong. OP, please pass the submission before posting here .


  • 0
    W

    This solution is wrong. Please fix it or delete it, because it is one of the "highly-voted" solutions.


  • 0
    Z

    @ccpromise there may be some problems. How can you make sure that you change the dic[tmp].back() is the index you need to change?


  • 3
    E
    dic[tmp].push_back(idx) 
    

    should be modified into:

    auto it = upper_bound(dic[tmp].begin(),dic[tmp].end(),idx);
    dic[tmp].insert(it,idx);
    

    Then it will pass the test cases. The problem is exactly as shown in @ccpromise 's answer


  • 1
    C

    I was thinking in the same way when I first saw this problem. I then realize that the array.back() may not coorelate with dict[X].back().
    For example, {1,3,2,2}.
    Map:
    1: 0
    2: 2 ,3
    3: 1
    after delete 1 {3, 2 ,2}
    Map
    1:
    2: 2, 0
    3: 1

    Now you want to delete 3 {2,2}
    Map
    1:
    2: 2, 1
    3:

    Now you see, the map[2]'s mapping is wrong. There is no index 2 in the final array {2,2}


  • 0
    J

    Status: Runtime Error
    @ccpromise said in C++ solution using map and vector with detailed explanation:

    class RandomizedCollection {
    private:
    map<int, vector<int>> dic;
    vector<int> arr;

    public:
    RandomizedCollection() {
    }

    bool insert(int val) {
        arr.push_back(val);//add val in arr
        dic[val].push_back(arr.size() - 1);//add its index in dic[val]
        return dic[val].size() == 1;
    }
    
    bool remove(int val) {
        if(dic[val].size() == 0)
        {
            return false;
        }
        int idx = dic[val].back();//arr[idx] = val
        dic[val].pop_back();
       //swap arr[idx] and arr[arr.size()-1] if idx != arr.size()-1
       //modify the dic at the same time.
        if(arr.size() - 1 != idx);
        {
            int tmp = arr.back();
            arr[idx] = tmp;
     //the new index of tmp is now idx, so modify the dic accordingly.
            dic[tmp].pop_back();
            dic[tmp].push_back(idx);
        }
       //remove the last element in arr
        arr.pop_back();
        return true;
    }
    
    int getRandom() {
        return arr[rand()%arr.size()];
    }
    

    };


  • 0
    M

    I think this solution is wrong because when you try to swap the last element (in your code is "tmp") and element val in the array, you need to remove the index of the last element from dic[tmp], and then add index "idx" into it. Your code "dic[tmp].pop_back( )" can't guarantee the correct last index is removed: at each iteration you put "idx" at the end of the vector so next time you operate pop_back(), you pop out "idx" in the last round but not the index of last element in this round.


Log in to reply
 

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