Problem solving with programming: Duplicate elements in array at given distance

Problem solving with programming: Duplicate elements in array at given distance

Pages Duplicate elements in array at given distance Given an array of numbers A, which might contain duplicate elements,  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.

Read full article from Problem solving with programming: Duplicate elements in array at given distance