# Find duplicates within a range k in an array

Posted in  Vinay Khatri
Last updated on November 30, 2023

## Problem

You are given an array of integers and a number k. You need to check if duplicates exist within distance of k in an array.

#### Sample Input

`[1, 2, 1, 3]  k = 2`

#### Sample Output

`True`

## Approach

We can store the value of an element as a key and its index as the value in a map. If we come to an element that has duplicates and any of the duplicates come within range ``` k ``` in an array, we find the duplicates within a given range. The time complexity of this approach is O(N) and space complexity is also O(N) due to the creation of a map.

### C++ Programming

```#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

bool solve(vector<int> &arr, int k)
{

unordered_map<int, int> mp;

for (int i = 0; i < arr.size(); i++)
{

if (mp.find(arr[i]) != mp.end())
{

if (i - mp[arr[i]] <= k) {
return true;
}
}

mp[arr[i]] = i;
}

return false;
}

int main()
{
vector<int> arr = { 1, 2, 1, 3 };
int k = 2;

if (solve(arr, k)) {
cout << "True";
}
else {
cout << "False";
}

return 0;
}```

#### Output

`True`

### Python Programming

```def solve(arr, k):

mp = {}

for i, element in enumerate(arr):

if element in mp:

if i - mp.get(element) <= k:
return True

mp[element] = i

return False

arr = [1, 2, 1, 3]
k = 2

if solve(arr, k):
print("True")
else:
print("False")```

#### Output

`True`

### Java Programming

```import java.util.HashMap;
import java.util.Map;

class Main
{
public static boolean solve(int[] arr, int k)
{

Map<Integer, Integer> mp = new HashMap<>();

for (int i = 0; i < arr.length; i++)
{
if (mp.containsKey(arr[i]))
{
if (i - mp.get(arr[i]) <= k) {
return true;
}
}

mp.put(arr[i], i);
}

return false;
}

public static void main(String[] args)
{
int[] arr = {1, 2, 1, 3 };
int k = 2;

if (solve(arr, k)) {
System.out.println("True");
}
else {
System.out.println("False");
}
}
}```

#### Output

```True
```