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] == nums[j] and the absolute difference between i and j is at most k (i.e., |i - j| ≤ k).

• You must return true if such a pair exists, otherwise return false.
• Each element in nums can be reused only at different indices (i.e., you cannot use the same index twice).
• The input constraints are typically: 1 ≤ nums.length ≤ 105 and -109 ≤ nums[i] ≤ 109.

Thought Process

To solve this problem, first consider the brute-force approach: for every element, check all other elements within k indices to see if any are equal. However, this quickly becomes inefficient for large arrays because it requires nested loops and many repeated comparisons.

To optimize, think about how you might keep track of the numbers you've seen so far and their positions. If you could instantly know whether a duplicate of the current number exists within the last k indices, you could answer the question much faster. This leads to the idea of using a data structure for quick lookups, such as a hash map (dictionary).

The hash map will store each number as a key and its most recent index as the value. As you iterate through the array, you can check if the current number is already in the map and whether the difference in indices is at most k. If so, return true. Otherwise, update the map with the latest index for that number.

Solution Approach

• Step 1: Initialize an empty hash map (or dictionary) to store numbers and their most recent indices.
• Step 2: Iterate through the array using a single loop. For each index i and value num:
  • Check if num is already in the hash map.
  • If it is, compute the difference between the current index i and the index stored in the map.
  • If the difference is less than or equal to k, return true immediately.
  • Otherwise, update the hash map with the current index for num.
• Step 3: If the loop completes without finding such a pair, return false.
• Why use a hash map? Because lookups and updates are on average O(1), making the solution efficient even for large arrays.
• Alternative: You could also use a sliding window with a set to keep only the last k elements, but the hash map approach is more direct for this problem.

Example Walkthrough

Consider the input nums = [1, 2, 3, 1] and k = 3:

1. At index 0, value is 1. Hash map: {1: 0}
2. At index 1, value is 2. Hash map: {1: 0, 2: 1}
3. At index 2, value is 3. Hash map: {1: 0, 2: 1, 3: 2}
4. At index 3, value is 1. 1 is already in the map at index 0. 3 - 0 = 3 ≤ 3, so return true.

The process stops as soon as the duplicate within k indices is found.

Time and Space Complexity

• Brute-force:
  • Time: O(nk), because for each element you might check up to k neighbors.
  • Space: O(1), as no extra data structures are used.
• Optimized (Hash Map):
  • Time: O(n), because you traverse the array once and each lookup/update in the hash map is O(1).
  • Space: O(min(n, k)), since the hash map holds at most one entry per unique value, potentially up to n entries in the worst case.

Summary

The key insight is to use a hash map to efficiently track the most recent index of each number. This allows you to check for duplicates within k indices in constant time per element, reducing the overall time complexity from O(nk) to O(n). The approach is both simple and powerful, making it well-suited for large input sizes.

Code Implementation

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        num_indices = {}
        for i, num in enumerate(nums):
            if num in num_indices and i - num_indices[num] <= k:
                return True
            num_indices[num] = i
        return False
      

class Solution {
   public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> num_indices;
        for (int i = 0; i < nums.size(); ++i) {
            if (num_indices.count(nums[i]) && i - num_indices[nums[i]] <= k) {
                return true;
            }
            num_indices[nums[i]] = i;
        }
        return false;
    }
};
      

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> numIndices = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (numIndices.containsKey(nums[i]) && i - numIndices.get(nums[i]) <= k) {
                return true;
            }
            numIndices.put(nums[i], i);
        }
        return false;
    }
}
      

var containsNearbyDuplicate = function(nums, k) {
    const numIndices = new Map();
    for (let i = 0; i < nums.length; i++) {
        if (numIndices.has(nums[i]) && i - numIndices.get(nums[i]) <= k) {
            return true;
        }
        numIndices.set(nums[i], i);
    }
    return false;
};