Sharing my 40ms C++ solution using unordered_map


  • 0
    T
    class Solution {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            unordered_map<int, vector<int>> myMap;
            int i, n = nums.size();
            for(i=0; i<n; i++)
                myMap[nums[i]].push_back(i);
            
            vector<vector<int>> mapVector;
            for(auto x=myMap.begin(); x!=myMap.end(); x++)
            {
                if(x->second.size() > 1)
                    mapVector.push_back(x->second);
            }
            
            int j;
            for(i=0; i<mapVector.size(); i++)
            {
                sort(mapVector[i].begin(), mapVector[i].end());
                int distance = INT_MAX;
                for(j=1; j<mapVector[i].size(); j++)
                    distance = min(distance, mapVector[i][j] - mapVector[i][j-1]);
                
                if(distance <= k)
                    return true;
            }
            
            return false;
        }
    };

Log in to reply
 

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