## Problem Statement

You are given an unsorted array that may contain duplicates. A number k that is less than the size of the array is also provided. Write a function that takes an array, an integer k, and the size of an array n, as input and the function returns true if the array contains duplicates within k distance.

Must Recommended Topic, __Hash Function in Data Structure____.__

**Examples: **

**Input: **

`k = 2, arr[] = {2, 2, 1, 4, 1, 2}`

**Output:**

`true`

2 is repeated at distance 2.

**Input: **

`k = 3, arr[] = {9, 2, 1, 8, 4, 5}`

**Output:**

`false`

**Input:**

`k = 4, arr[] = {6, 2, 8, 6, 5}`

**Output: **

`true`

6 is repeated at distance 4.

## Naive approach

The first and easiest solution is Running two loops. The inner loop checks all items that are within k distance of "arr[i]" after the outer loop chooses every element "arr[i]" as a starting element. This solution has a time complexity (kn).

### Algorithm

- Create a function that takes arr[], k, and n as parameters.
- Run the first loop to traverse the whole array.
- Inside this loop, start another loop to search next k-1 elements
- if their duplicates are present, return True
- Else False

Let's take an example to better understand the algorithm.

**k = 2, arr[] = {9,5,5,4}**

**Step 1: **Take Array as input

**Step 2: **Take the first element of the array = 9 and initialize a variable w=k

**Step 3:** Match with the next element and if the element is not equal reduce the value of w

**Step 4:** if the value of w<0, come out of the loop and take another element of the array and perform step 3 and step 4.

**Step 5:** The element 5 matches with the next element and returns Yes.

### Code in C++

Implementation in C++ to check if a given array contains duplicate elements within k distance from each other.

```
#include <bits/stdc++.h>
using namespace std;
bool checkDuplicates(int arr[], int n, int k)
{
for (int i = 0; i < n; i++) {
int window = k;
for(int j=i+1;window>0 && j<n;j++){
if (arr[i] == arr[j])
return true;
window--;
}
}
return false;
}
int main()
{
int arr[] = { 14, 4, 7, 4, 9, 4, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
if (checkDuplicates(arr, n, 3))
cout << "Yes";
else
cout << "No";
}
```

**Output**

`Yes`

### Code in Java

Implementation in Java to check if a given array contains duplicate elements within k distance from each other.

```
public class Main
{
public static boolean checkDuplicates(int[] arr, int n, int k)
{
for (int i = 0; i < n; i++)
{
int window = k;
for (int j = i + 1;window > 0 && j < n;j++)
{
if (arr[i] == arr[j])
{
return true;
}
window--;
}
}
return false;
}
public static void main(String[] args)
{
int[] arr = {14, 4, 7, 4, 9, 4, 6};
int n = arr.length;
if (checkDuplicates(arr, n, 3))
{
System.out.print("Yes");
}
else
{
System.out.print("No");
}
}
}
```

**Output**

`Yes`

### Code in Python

Implementation in Python to check if a given array contains duplicate elements within k distance from each other.

```
def main():
arr = [14, 4, 7, 4, 9, 4, 6]
n = len(arr)
if Globals.checkDuplicates(arr, n, 3):
print("Yes", end = '')
else:
print("No", end = '')
class Globals:
@staticmethod
def checkDuplicates(arr, n, k):
for i in range(0, n):
window = k
j = i+1
while window>0 and j<n:
if arr[i] == arr[j]:
return True
window -= 1
j += 1
return False
if __name__ == "__main__":
main()
```

**Output**

`Yes`

**Time complexity**: 0(kn)

There are nested loops present in the solution and the time complexity will depend on the condition of the loop. The first loop is running n time and the second one depends on the parameter k hence time complexity will be 0(kn).

**Space Complexity-O(1)**

We haven't stored the value anywhere in the code hence space complexity will be O(1)