K Distance Duplicate¶

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.

Method 1 -> 2 loops -> O(kn)¶

Method 2 -> Hashing¶

Θ(n)

bool checkDuplicatesWithinK(int arr[], int n, int k) 
{ 
    unordered_set<int> myset; 

    for (int i = 0; i < n; i++) 
    {  
        if (myset.find(arr[i]) != myset.end()) 
            return true; 

        myset.insert(arr[i]); 

        if (i >= k) 
            myset.erase(arr[i-k]); 
    } 
    return false; 
}