Check if a given array contains duplicate elements within k distance from each in C++

Here we will see how to check whether an unsorted array has duplicate elements within k distance from each other or not. Suppose a list of elements is {1, 2, 3, 1, 4, 5}, here if k = 3, then the program will return true, as the distance between two 1s is 3.

We will solve this using a hash table. The steps will be like below −

• Create one empty hash table
• For each index i, let the element e = arr[i] in the list, do
  • if e is present in the hash table, then return true
  • otherwise, add e to hash table, and remove (i-k)th element from the hash table if it exists, when i >= K.

Example

 Live Demo

#include<iostream> #include<set> using namespace std; bool hasDuplicateWithDistK(int arr[], int n, int k) {    set<int> element_set;    for (int i = 0; i < n; i++) {       if (element_set.find(arr[i]) != element_set.end())          return true;       element_set.insert(arr[i]);       if (i >= k)          element_set.erase(arr[i-k]);    }    return false; } int main () {    int arr[] = {10, 5, 3, 4, 3, 5, 6};    int n = sizeof(arr) / sizeof(arr[0]);    if (hasDuplicateWithDistK(arr, n, 3))       cout << "Duplicate element has found";    else       cout << "Duplicate element has not found"; }

Output

Duplicate element has found