Contains Duplicate II

Problem Description

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.

Key Insights

• We need to identify if any two elements in the array are equal and within a specified index difference of k.
• A hash table (or set) can be used to store the elements as we iterate through the array to efficiently check for duplicates.
• The sliding window technique can help maintain a range of indices to ensure the distance condition is satisfied.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(min(n, k))

Solution

To solve the problem, we can use a hash table to keep track of the values we encounter as we iterate through the array. The algorithm follows these steps:

1. Initialize an empty hash table (or set).
2. Iterate through the nums array with an index i.
3. For each element, check if it is already in the hash table.
   • If it is, check the index difference. If the difference is less than or equal to k, return true.
   • If it is not, add the element to the hash table.
4. If the size of the hash table exceeds k, remove the oldest element to maintain the size.
5. If the loop completes without finding any valid pairs, return false.

Code Solutions