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