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

Difficulty Level Easy
Frequently asked in Amazon Avalara Citadel FreeCharge HackerRank Snapchat Snapdeal
Array HashViews 3679

The problem “Check if a given array contains duplicate elements within k distance from each other” states that we have to check for duplicates in given unordered array within the range of k. Here the value of k is smaller than the given array.

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

Examples

K = 3   arr[] = {1, 2, 3, 4, 5, 2, 1}
False
K = 2   arr[] = {3, 4, 3, 1, 1, 2, 6}
True

Explanation

We have two methods to solve this problem. The simpler one is to run two loops in which the first loop will pick every element as a starting element for the second loop ‘Inner loop’. After that, the second loop will compare the starting element with all the elements within the range of ‘k’. But this solution is not that efficient it takes time complexity of O(k*n).

But we have another more efficient method which can solve the problem in O(n) time complexity called hashing. In the hashing method, we will traverse all the elements of the array and we will check if the element is present in it or not. If the element is in there then we will return ‘True.’ Else we will add it to the hash and remove the arr[i-k] element from the hash if ‘i’ is greater than or equal to ‘k’.

Algorithm to Check if a given array contains duplicate elements within k distance from each other

  1. First, create the empty hash set in which we will store the elements of the array.
  2. Traverse all elements of the array from left to right.
  3. Check if the element is present in hash or not.
    • If it’s in there then return “true.”
    • Else add that element to the hash.
  4. After that remove the arr[i-k] element from hash if ‘I’ is greater or equal to ‘k’.

 

We have an array ‘arr[]’ with some element in it and a value k which is the range in which we have to find duplicates if there Is any so will use hash set to store the elements in it first we will add elements of the array in our hash set one by one if the element is already in the hash set then it will return true and break the loop else it will continuously insert the elements in the set and remove arr[i-k] element from the set.

Code

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

#include<iostream>
#include<unordered_set>
using namespace std;

bool Check_Duplicates(int a[], int n, int k)
{

    unordered_set<int> D_set;

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

        D_set.insert(a[i]);
        if (i >= k)
            D_set.erase(a[i-k]);
    }
    return false;
}

int main ()
{
    int a[] = {1, 2, 3, 4, 1};
    int k = 5;
    cout << ((Check_Duplicates(a, 5, k)) ? "Yes" : "No");
}

Yes

Java code to Check if a given array contains duplicate elements within k distance from each other

import java.util.*;
class D_Class
{
    static boolean Check_Duplicates(int a[], int k)
    {

        HashSet<Integer> D_set = new HashSet<>();

        for (int i=0; i<a.length; i++)
        {
            if (D_set.contains(a[i]))
                return true;

            D_set.add(a[i]);
            if (i >= k)
                D_set.remove(a[i-k]);
        }
        return false;
    }

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

        if (Check_Duplicates(a, k))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Yes

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Using a Hash Set allows solving the problem in linear time. Since using hash set enhances the ability to search, delete and insert data efficiently.

Space Complexity

O(k) where “k” is the number of elements in the window that needs to be looked upon.

Translate »