Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <= k.
Example 1:
Input: nums = [1,2,3,1], k = 3
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1
Output: true
Example 3:
Input: nums = [1,2,3,1,2,3], k = 2
Output: false
Constraints:
- 1 <= nums.length <= 105
- -109 <= nums[i] <= 109
- 0 <= k <= 105
My Solution
One way to solve this problem is to maintain a HashMap that stores the latest mapping from a number to its index. We iterate through the array and if we have seen the number before, or in other words it is in the HashMap, we check if the difference in indices between the current element and the previous occurrence of the element is less than k. If it is we return true. At every iteration we update the index of the element in the HashMap.
Time complexity would be O(n) because we scan the array once. Space complexity is also O(n) because we need to maintain the HashMap.
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer,Integer> idx = new HashMap<>();
int n = nums.length;
for (int i = 0; i < n; i++) {
if (idx.containsKey(nums[i]) && (i-idx.get(nums[i]) <= k)) {
return true;
}
idx.put(nums[i], i);
}
return false;
}
}