The idea is to iterate over the input array and use an unordered map to store the last seen position of the numbers. For each number, if it already exists in the map and the current index - last seen index (stored in map) is <= k then we have found the answer to be true.
bool containsNearbyDuplicate(vector<int>& nums, int k) {
// sanity check
if(nums.size()==0 || nums.size()==1 || k==0){
return false;
}
unordered_map<int,int> umap;
for(int i=0; i<nums.size(); i++){
if(umap.find(nums[i]) != umap.end() && i - umap[nums[i]]<=k)
return true;
umap[nums[i]] = i;
}
return false;
}
Time Complexity O(n)
We can further optimize space by using an unordered set instead of an unordered map. While iterating through index i, the set will only contain numbers from index i-k to i-1.
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> s;
// sanity check
if (k <= 0) return false;
if (k >= nums.size()) k = nums.size() - 1;
for (int i = 0; i < nums.size(); i++) {
if (i > k) s.erase(nums[i - k - 1]);
if (s.find(nums[i]) != s.end()) return true;
s.insert(nums[i]);
}
return false;
}
Time complexity: O(n)