0

This is a leetcode question: 219. Contains Duplicate II

I used the insert function for hash map. Can someone please tell me what is wrong with the first code?

//wrong solution
class Solution {
public:
   bool containsNearbyDuplicate(vector<int>& nums, int k) {
       unordered_map<int,int>m;
       int n=nums.size();
       for(int i=0;i<n;i++){
          if(m.find(nums[i])!=m.end() && abs(i-m[nums[i]]) <=k) return true;
          m.insert(pair<int,int>(nums[i],i));                                      //this is the faulty part
       }
       return false;
   }
};

//Right 
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int>m;
        int n=nums.size();
        for(int i=0;i<n;i++){
           if(m.find(nums[i])!=m.end() && abs(i-m[nums[i]]) <=k) return true;
           m[nums[i]]=i; 
        }
        return false;
    }
};
itachi_uchiha
  • 11
  • 2
  • 1
    Does this answer your question? [insert vs emplace vs operator\[\] in c++ map](https://stackoverflow.com/questions/17172080/insert-vs-emplace-vs-operator-in-c-map) – Raymond Chen May 20 '22 at 19:35

1 Answers1

2

The std::map and std::unordered_map types have slightly unusual behavior for their insert functions. Specifically, if you use insert to add a key/value pair to the map, and the key already existed in the map, the insert operation doesn't actually add anything. Instead, it'll hand back an iterator to the element that was already there. Therefore, your first version of the code doesn't actually do what it looks like it does, since the insert call won't change the existing value.

On the other hand, using operator[] (the square brackets) doesn't do this. Selecting a key with operator[] either inserts a key/value pair and then returns a reference to the value, or returns a reference to the existing value. That's why the second version does work - it'll replace existing values with new ones when needed.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065