Hashing: Given a array, you need to find a duplicate within k distance in the array.

Problem Statement:

You are given an array and an integer K.

You need to check if there exist 2 indices i and j, such that arr[i] == arr[j] and |i-j| <= k.

Return yes or no.

Example:

Input:

k = 3

arr = [1, 2, 3, 1, 4, 5]

Output:

Yes

Element 1 is present at index 0 and 3

Solution 1: Brute force approach

In brute force approach, you need to use 2 loops.

Outer loop picks an element and inner loop will loop through the whole array and compare the element.

If the element is found within the k distance, then return true.

Time Complexity: O(n*k)
Space Complexity: O(1)

Solution 2: Hash Set

We will use set to keep track of the elements inside the current window of K size.

Iterating over the array, if the element is present in the set, then duplicate is found and return true.

else add the element into the set.

If the set grows larger than size k, then remove the element outside the window.

If no duplicate found, return false.

Time Complexity: O(n)
Space Complexity: O(k)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <unordered_set>
using namespace std;

bool solution_1(vector<int> arr, int k)
{

    for (int i = 0; i < arr.size(); i++) {
      
        for (int c = 1; c <= k && (i + c) < arr.size(); c++) {
            int j = i + c;
          
            if (arr[i] == arr[j])
              return true;
        }
    }
    return false;
}

bool solution_2(vector<int> arr, int k) {

    unordered_set<int> window;

    for (int i = 0; i < arr.size(); i++) {
        if (window.count(arr[i])) {
            return true;
        }
        window.insert(arr[i]);

        if (window.size() > k) {
            window.erase(arr[i - k]);
        }
    }
    return false;
}

int main()
{
    vector<int> arr = {1, 2, 3, 1, 4, 5};
    
    if (solution_1(arr, 3))
        cout << "Yes";
    else
        cout << "No";
    
    cout<<endl;
    
    if (solution_2(arr, 3))
        cout << "Yes";
    else
        cout << "No";

    return 0;
}

Output

Yes
Yes