Problem:

Check if a given array contains duplicate elements within k distance from each other
Given an unsorted array that may contain duplicates. Also given a number k which is smaller than size of array. Write a function that returns true if array contains duplicates within k distance.

Example:
Input: k = 3, arr[] = {1, 2, 3, 4, 1, 2, 3, 4}
Output: false
All duplicates are more than k distance away.

Input: k = 3, arr[] = {1, 2, 3, 1, 4, 5}
Output: true
1 is repeated at distance 3.

Input: k = 3, arr[] = {1, 2, 3, 4, 5}
Output: false

Input: k = 3, arr[] = {1, 2, 3, 4, 4}
Output: true

Solution:

– Task Hash (specially HashSet – so duplicate will not allowed)
– Iterate all element one by one in stack
– Put first k elements of array to set and check for if its already represent in set or not if yes then return true
– if loop counter greater than k then remove first inserted element (i – k th) from array.

Latest Source Code:
Github: ArrayDuplicateItemWithInKDistance.java

Output:

 Array : [1, 2, 3, 4, 1, 2, 3, 4], K= 3 : false
Array : [1, 2, 3, 1, 4, 5], K= 3 : true
Array : [1, 2, 3, 4, 5], K= 3 : false
Array : [1, 2, 3, 4, 4], K= 3 : true