Dare2Solve
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.
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:
k
, return true
.Return false
: If we complete the iteration without finding any valid pairs, return false
.
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.
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.
class Solution {
public:
bool containsNearbyDuplicate(std::vector<int>& nums, int k) {
std::unordered_map<int, int> 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;
}
};
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
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> 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;
}
}
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
};