🎨Now live: Try our Free AI Image Generation Feature

Intuition
To determine if there are two distinct indices i
and j
in the array nums
such that nums[i] == nums[j]
and the absolute difference between i
and j
is less than or equal to k
, we can utilize a hash map (or dictionary) to keep track of the indices of the elements we encounter as we iterate through the array. This allows us to efficiently check if we have seen the same element within the desired range.
Approach
- Initialize a dictionary: We will use a dictionary to store each element in the array and its corresponding index as we iterate through the array.
- Iterate through the array:
For each element in the array:
- Check if the element is already in the dictionary.
- If it is, calculate the difference between the current index and the index stored in the dictionary.
- If the difference is less than or equal to
k
, returntrue
. - Update the dictionary with the current element and its index. - Return
false
: If we complete the iteration without finding any valid pairs, returnfalse
.
Complexity
Time Complexity:
O(n), where n
is the number of elements in the array. We traverse the array once, and each dictionary operation (insertion and lookup) is O(1) on average.
Space Complexity:
O(n) in the worst case, where n
is the number of elements in the array. In the worst case, all elements are unique and stored in the dictionary.
Code
C++
class Solution {
public:
bool containsNearbyDuplicate(std::vector& nums, int k) {
std::unordered_map map;
for (int i = 0; i < nums.size(); i++) {
if (map.find(nums[i]) != map.end()) {
if ((i - map[nums[i]]) <= k) {
return true;
}
}
map[nums[i]] = i;
}
return false;
}
};
Python
class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
num_map = {}
for i in range(len(nums)):
if nums[i] in num_map:
if (i - num_map[nums[i]]) <= k:
return True
num_map[nums[i]] = i
return False
Java
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
if ((i - map.get(nums[i])) <= k) {
return true;
}
}
map.put(nums[i], i);
}
return false;
}
}
JavaScript
var containsNearbyDuplicate = function (nums, k) {
let map = new Map()
for (let i = 0; i < nums.length; i++) {
if(map.has(nums[i])){
if(( i - map.get(nums[i]) ) <= k)return true
}map.set(nums[i] , i)
}return false
};