Problem Description
Given an integer array nums and an integer k, determine if there are two distinct indices i and j in the array such that nums[i] equals nums[j] and the absolute difference between i and j is at most k.
Key Insights
- Use a hash table (or a sliding window) to keep track of the most recent index where each number appears.
- For every element, if it is already in the hash table, check the difference between the current index and its previously stored index.
- If the difference is within k, return true immediately.
- Otherwise, update the index for the element.
- Alternatively, maintain a sliding window (using a set) of size at most k to check for duplicates in the current window.
Space and Time Complexity
Time Complexity: O(n) — where n is the number of elements in nums, since each element is processed once. Space Complexity: O(min(n, k)) — using a hash table or set that stores at most k elements at any time.
Solution
We leverage a hash table to store numbers and their most recent indices. As we iterate through the array, we check if the current number is already in the table. If so, we examine the distance between the current index and the saved index. Should this distance be at most k, we can immediately return true. If not, we update the stored index for that number. This method ensures only a single pass through the array is required. An alternative approach is to use a sliding window implemented via a set, where we maintain a window of size k. If a duplicate is encountered within the window, we return true.