CODEWITHSUNDEEP
c++stlunordered-map
avishek kumar
avishek kumar

Reputation: 31

Getting unexpected result in unordered map

Why I am getting output as 13 11 9 7 5 3 5 7 9 11 13 12 10 8 6 4 when my nums vector is [1,3,5,7,9,11,13]. I think it should be one of the combination of 1 3 5 7 9 11 13.

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int,int> m;
        for(auto e:nums){
            m[e]++;
        }
        int maxLen=0;
        for(auto it=m.begin();it!=m.end();it++)
        {
            int ele=it->first;
            cout<<ele<<" ";
            if(m[ele-1])
                maxLen=max(maxLen,(m[ele]+m[ele-1]));
            if(m[ele+1])
                maxLen=max(maxLen,(m[ele]+m[ele+1]));
                
        }
        return maxLen;
        
    }
};

Upvotes: 0

Views: 81

Answers (1)

Useless
Useless

Reputation: 67713

You have two problems:

  1. if(m[ele-1]) will insert a new (default-constructed) element with key ele-1 if it wasn't already there, as documented (and the ele+1 version does the same)

    This is a logic error, in that your program is doing something that, although well-defined, is not what you wanted. You should use find if you want to find out whether something exists without default-constructing it.

  2. When you mutate the container (by inserting an element instead of finding it) - this may invalidate the iterators you're using to walk the container. Again, see the same documentation:

    If an insertion occurs and results in a rehashing of the container, all iterators are invalidated.

    This is a more serious error, because continuing to use those iterators at all is Undefined Behaviour. It's not a logic error, but a bug.

Reasonable code might look like

        for(auto it=m.begin(); it!=m.end(); it++)
        {
            cout << it->first <<" ";
            auto pred = m.find(it->first - 1);
            auto succ = m.find(it->first + 1);

            if(pred != m.end())
                maxLen=max(maxLen, it->second + pred->second);
            if(succ != m.end())
                maxLen=max(maxLen, it->second + succ->second);       
        }

Upvotes: 1

Related Questions