Contains Duplicate
You have been given an array “ARR” of integers and an integer ‘K’. Your task is to find a pair of distinct indices ‘i’ and ‘j’ such that ARR[i] == ARR[j] and | i - j |

Question

Contains Duplicate

You have been given an array “ARR” of integers and an integer ‘K’. Your task is to find a pair of distinct indices ‘i’ and ‘j’ such that ARR[i] == ARR[j] and | i - j | <= ‘K’.

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. The 'T' test cases follow.

The first line of each test case will contain two integers ‘N’ and ‘K’ where ‘N’ is the number of elements in the array, and the integer ‘K’ is described as above.

The second line of each test case will contain ‘N’ space-separated integers denoting the elements in the array.

Output Format :

For each test case, print “Yes” (without quotes) if a pair of such distinct indices (described in the problem statement) exists otherwise print “No” (without quotes).

Output for every test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= N <= 10000
1 <= K <= 10000
0 <= ARR[i] <= 10^9

Where 'ARR[i]' denotes the ith element of the given array.

Time limit: 1 sec

Accepted Answer

I used HashMap to store each integer and its count. If the integer is already in the HashMap then returned false.

Accepted Answer

Naive Approach

The basic idea of this approach is to iterate through all the possible pairs of indices and check if duplicate elements exist satisfying the given constraint in the problem statement.

Consider the following steps:

Create a loop and start traversing the given array/list using a variable ‘i’ such that 0 <= i < ‘N’.
In a nested loop, start traversing the array/list using a variable ‘j’ such that 0 <= j < i and for each pair of (i, j) check:
1. If | i - j | <= ‘K’ and ARR[i] = ARR[j], then duplicate elements with given constraint exist in the array/list, therefore return “Yes”.
Else, return false.

Space Complexity: O(1)Explanation:

O(1)

Since we are not using any extra space other than the few variables. So the overall space complexity will be O(1).

Time Complexity: O(n^2)Explanation:

O(N^2), where ‘N’ is the number of elements in the given array/list.

Since we are trying to consider every pair of indices in the given array/list. So the overall time complexity will be O(N^2).

Python (3.5)

"""

    Time complexity: O(N ^ 2)

    Space complexity: O(1)



    Where N is the length of the given array/list.

"""





def containsNearbyDuplicates(arr, k):



    #   Start traversing the array.

    for i in range (len(arr)):

        for j in range(i):

            #    Check if current pair satisfies the condition.

            if (abs(i - j) <= k and arr[i] == arr[j]):

                return True



    return False



    pass

Java (SE 1.8)

/*

    Time Complexity : O(N^2)

    Space Complexity : O(1)



    Where 'N' is the length of the given array/list.



*/



import java.util.ArrayList;



public class Solution 

{

    public static boolean containsNearbyDuplicates(ArrayList arr, int k) 

    {

        //    Start traversing the array.

        for (int i = 0; i < arr.size(); i++) 

        {

            for (int j = 0; j < i; j++) 

            {

                int temp = arr.get(j);

                //    Check if current pair satisfies the condition.

                if (Math.abs(i - j) <= k && arr.get(i).equals(arr.get(j))) 

                {

                    return true;

                }

            }

        }



        return false;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity : O(N^2)

    Space Complexity : O(1)

    

    Where 'N' is the length of the given array/list.



*/



bool containsNearbyDuplicates(vector &arr, int k)

{

	//    Start traversing the array.

	for (int i = 0; i < arr.size(); i++)

	{

		for (int j = 0; j < i; j++)

		{

			//    Check if current pair satisfies the condition.

			if (abs(i - j) <= k && arr[i] == arr[j])

			{

				return true;

			}

		}

	}



	return false;

}

Accepted Answer

HashMap based approach.

The basic idea of this approach is to use a HashMap to store the index of the elements of the array/list so that we can very efficiently check if a particular element exists in the array/list or not. We will maintain a HashMap to store the pair. Next, we will start traversing the array/list and check if the current element exists in the HashMap and the absolute difference of the index of that element and the current index is less than or equal to ‘K’. And each iteration will update the HashMap with a pair of current elements and index.

Consider the following steps:

Create a HashMap say indexofElement.
Start traversing the array/list using a variable ‘i’ such that 0 <= ‘i’ <= ‘N’ - 1
At each iteration, check if the current element (ARR[i]) exists in the HashMap
1. If exists get the index and store it in a variable ‘j’ i.e.

‘j’ = indexOfElement[ARR[i]]

If | i - j | <= ‘K’ then return true since we have found a pair of indices (i, j) which satisfies the condition ARR[i] = ARR[j] and | i - j | <= ‘K’.
Update the HashMap with a pair of the current element and current index, i.e.

indexOfElement[ARR[j]] = j

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of elements in the given array/list.

Since we are using a HashMap to store the pair of elements and its index and in the worst case where all the elements are distinct, the HashMap will store all the elements. So the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of elements in the given array/list.

Since we are using a HashMap to store the pair of elements and its index and operations like insert and find takes O(1) time in the average case. So the overall time complexity will be O(N).