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

Hello everyone, in this tutorial, we will check if a given array contains duplicate elements within k distance from each other in C++.
Examples
Input 1 :
a[] = {1,4,2,1,5}
k=2
Output 1 :
Duplicate found

Input 2 :
a[] = {1,4,2,3,5}
k=2
Output 2 :
No Duplicate found

We can solve this problem using two for loops but then its time complexity will become O(nk). But to make it more efficient we will solve this problem using hashing so that our time complexity becomes O(n).

Algorithm :

1. Firstly, create an empty hash table
2. Then we will traverse from i =0 to i<n and check
   if the arr[i] is not equal to the last element of hash table
        return true
   else insert arr[i] in the hash table.
3. Now if i>= k then delete the element arr[i-k].
4. Lastly, If you don’t find any of them then return false

#include<bits/stdc++.h>

using namespace std;

bool duplicatesAtK(int arr[] , int n , int k)
{
    unordered_set <int> elementSet;
     for (int i = 0; i < n; i++) {
      if (elementSet.find(arr[i]) != elementSet.end())
         return true;
      elementSet.insert(arr[i]);
      if (i >= k)
         elementSet.erase(arr[i-k]);
   }
   return false;
}

int main()
{
    int n,d;
    std::cout<<"Enter the numbers of elements in array : ";
    std::cin>>n;
    
    int arr[n];
    std::cout<<"Enter the elements of array : ";
    for(int i=0 ; i<n ; i++)
        std::cin>>arr[i];
    
    std::cout<<"Enter the distance k : ";
    std::cin>>d;
    
    if(duplicatesAtK(arr,n,d))
        std::cout<<"Duplicate found";
    else
        std::cout<<"No Duplicate found";
    
    
}

Output 1 :

Enter the numbers of elements in array : 5 
Enter the elements of array : 2 1 3 2 4 
Enter the distance k : 3
Duplicate found

Output 2 :

Enter the numbers of elements in array : 5 
Enter the elements of array : 2 1 3 6 4 
Enter the distance k : 3
No Duplicate found

Also read,

1. condition_variable::wait in C++
2. Singleton in C++