Problem Statement

Given an array of integers nums and an integer k, return true if there are any two different indices i and j in the array where nums[i] == nums[j] and abs(i - j) <= k. Otherwise, return false.

Examples

Example 1:

• Input: nums = [10, 20, 10, 30], k = 1
• Output: false
• Explanation: The number 10 appears at positions 0 and 2. The difference between these positions is 2, which is not less than k.

Example 2:

• Input: nums = [5, 15, 25, 5, 35], k = 3
• Output: true
• Explanation: The number 5 appears at positions 0 and 3. The difference between these positions is 3, which is equal to k.

Example 3:

• Input: nums = [7, 8, 9, 7, 10, 11], k = 4
• Output: true
• Explanation: The number 7 appears at positions 0 and 3. The difference between these positions is 3, which is less than to k.

Constraints:

• 1 <= nums.length <= 10⁵
• -10⁹ <= nums[i] <= 10⁹
• 0 <= k <= 10⁵

Solution

To solve this problem, we'll use a hashmap to keep track of the last seen position of each number as we iterate through the array. This approach is efficient because it allows us to check in constant time whether a number has appeared before and whether the difference between the current position and the last seen position is less than or equal to k. By using a hashmap, we ensure that we only traverse the array once, making our solution fast.

This approach is effective because it minimizes the number of operations required to find the solution, ensuring that we can handle large arrays efficiently.

Step-by-step Algorithm

• Initialize an empty hashmap to store the last seen position of each number.
• Loop through the array with an index i.
  • For each number nums[i], check if it is already in the hashmap.
    • If it is, check if the difference between the current index i and the stored index is less than or equal to k.
      • If true, return true.
    • If it is not, or the difference is greater than k, update the hashmap with the current index.
• If the loop completes without finding any valid pairs, return false.

Algorithm Walkthrough

Using the input nums = [7, 8, 9, 7, 10, 11], k = 4:

1. Initialize hashmap: {}
2. Index 0, value 7:
   • 7 is not in hashmap.
   • Add 7 to hashmap with index 0: {7: 0}
3. Index 1, value 8:
   • 8 is not in hashmap.
   • Add 8 to hashmap with index 1: {7: 0, 8: 1}
4. Index 2, value 9:
   • 9 is not in hashmap.
   • Add 9 to hashmap with index 2: {7: 0, 8: 1, 9: 2}
5. Index 3, value 7:
   • 7 is in hashmap at index 0.
   • Check difference: 3 - 0 = 3, which is less than or equal to k.
   • Return true.