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
The problem asks whether there exist two distinct indices i
and j
in the input array nums
such that nums[i] == nums[j]
and abs(i - j) <= k
. In simpler terms: are there two identical numbers within a distance of k
indices from each other?
The most efficient approach uses a hash table (or dictionary in Python) to store the elements and their most recent indices. This approach leverages the properties of a hash table for fast lookups (O(1) on average). It's a variation of the sliding window technique, although the window size isn't fixed but implicitly defined by k
.
Algorithm:
d
.nums
array using a for
loop.nums[i]
:
nums[i]
exists as a key in d
.i
and the index stored in d
(the previous index of the same element).k
, it means we found two identical numbers within the distance k
. Return true
.d
or the difference is greater than k
, add (or update) the element and its current index i
into d
.false
.n
elements. However, if k
is much smaller than n
, the space used will be closer to O(k) because only elements within the window of size k
need to be stored.class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
d = {} # Hash table to store elements and their indices
for i, x in enumerate(nums):
if x in d and i - d[x] <= k: # Check if element exists and distance <= k
return True
d[x] = i # Update index for the element
return False
The other language implementations follow the same logic, differing only in syntax and specific data structures used (e.g., HashMap
in Java, unordered_map
in C++, Map
in TypeScript/JavaScript). The core algorithm remains consistent across all languages.