Check if a given array contains duplicate elements within k distance from each other - GeeksforGeeks
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. Examples: 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 A Simple Solution is to run two loops. The outer loop picks every element 'arr[i]' as a starting element, the inner loop compares all elements which are within k distance of 'arr[i]'. The time complexity of this solution is O(kn). We can solve this problem in Θ(n) time using Hashing. The idea is to one by add elements to hash. We also remove elements which are at more than k distance from current element.Read full article from Check if a given array contains duplicate elements within k distance from each other - GeeksforGeeks
