Contains Duplicate II [Easy] — Index Window HashMap
Sanjeev SharmaAdvertisement
Problem Statement
Return true if there are two distinct indices i, j in the array where nums[i] == nums[j] and |i-j| <= k.
Input: nums=[1,2,3,1], k=3 → true
Input: nums=[1,0,1,1], k=1 → true
Input: nums=[1,2,3,1,2,3], k=2 → false
Solutions
C++
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_map<int,int> last;
for(int i=0;i<nums.size();i++){
if(last.count(nums[i])&&i-last[nums[i]]<=k) return true;
last[nums[i]]=i;
}
return false;
}
Java
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer,Integer> last=new HashMap<>();
for(int i=0;i<nums.length;i++){
if(last.containsKey(nums[i])&&i-last.get(nums[i])<=k) return true;
last.put(nums[i],i);
}
return false;
}
Python
def containsNearbyDuplicate(nums: list[int], k: int) -> bool:
last = {}
for i, x in enumerate(nums):
if x in last and i - last[x] <= k:
return True
last[x] = i
return False
JavaScript
var containsNearbyDuplicate = function(nums, k) {
const last=new Map();
for(let i=0;i<nums.length;i++){
if(last.has(nums[i])&&i-last.get(nums[i])<=k) return true;
last.set(nums[i],i);
}
return false;
};
Complexity
- Time: O(n), Space: O(min(n,k))
Advertisement
