Contains Duplicate II

Problem Statement

The task is to check whether an integer array nums contains at least two distinct indices i and j such that the elements at these indices are equal (nums[i] == nums[j]), and the absolute difference between these indices is at most k (abs(i - j) <= k). If such indices exist, the function should return true, otherwise, it should return false. This problem essentially checks for duplicates within a specific range of indices in an array.

Examples

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

Approach and Intuition

1. Understand the Problem: We want to find out if there are two elements in nums such that they are equal and their indices are not farther apart than k.

2. Initial Thoughts:

   • A naive approach would be to check every possible pair in the array with a double loop, but this has a time complexity of O(n^2), which is impractical for large arrays.
   • An optimal approach would utilize hashing to keep track of elements and their indices efficiently.

3. Utilizing a Map:

   • Use a hash map (dictionary in Python) to map each element to its latest occurrence index as we iterate over the array.
   • For every new element, check if it is already in the hash map.
   • If the element is found, compare the current index with the stored index. If the difference does not exceed k, return true.
   • Update the hash map with the current index of the element for future comparisons.

4. Edge Cases:

   • If k is zero, immediate duplicates are needed at the same index which is not possible by definition of distinct indices.
   • Very large or very small values do not affect the logic but are included to understand the range of input conditions.

This approach ensures that we only keep track of the most recent index of each element and compare indices that are potentially within the required range, reducing unnecessary comparisons.

Solutions

public boolean hasCloseDuplicate(int[] arr, int k) {
    Set<Integer> hashSet = new HashSet<>();
    for (int idx = 0; idx < arr.length; ++idx) {
        if (hashSet.contains(arr[idx])) return true;
        hashSet.add(arr[idx]);
        if (hashSet.size() > k) {
            hashSet.remove(arr[idx - k]);
        }
    }
    return false;
}