How do we find if there are two elements A[i], A[j] such that i, j are distinct and the difference between them is at most k?
Look at the following examples.
1. A = [9, 5, 6, 9, 3, 0, 1], K =3
The answer is “Yes” because 9 is present at index 0, and 3
2. A = [10, 0, 10, 20, 30], K = 1
The answer is “No” because there are no duplicate elements at a distance less than or equal to 1
A simple and straight forward algorithm is to have two loops, the outer loop fixing one element, and the inner loop checks if that element exists within a distance of K. This algorithm runs in O(n2) in worst case.
Let us look at an efficient algorithm using the map data structure. The map stores the element as the key and it’s most recent index as it’s value. Here are the steps.
- For each element in the array
- Store the element and it’s index in the map if does not exist already.
- If already exists,
- Check if the difference between the recent index and current index is less than K.
- If so return true.
- Otherwise update the map with recent index
This algorithm runs in O(n log n) time, and take O(n) extra space for the map. Here is the C++ code given below. For the Python implementation checkout this link. For Java implementation check this link.