Check Duplicate
Given an array 'arr' of 'N' integers and an integer 'K'. The array 'arr' may contain duplicate integers. Return "true" if the array contains any duplicate element within the 'K' distance from each other, otherwise, return "false".

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the T test cases follow: The first line of each test case contains two single space-separated integers 'N', and 'K', denoting the size of the array 'arr' and the distance respectively. The second line of each test case contains 'N' single space-separated integers, elements of the array.

Output format :

For each test case, print “true” if the array contains any duplicate element within the 'K' distance from each other, otherwise, print "false". Result for each 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

Question

Check Duplicate

Given an array 'arr' of 'N' integers and an integer 'K'. The array 'arr' may contain duplicate integers. Return "true" if the array contains any duplicate element within the 'K' distance from each other, otherwise, return "false".

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run.

Then the T test cases follow:

The first line of each test case contains two single space-separated integers 'N', and 'K', denoting the size of the array 'arr'  and the distance respectively. 

The second line of each test case contains 'N' single space-separated integers, elements of the array.

Output format :

For each test case, print “true” if the array contains any duplicate element within the 'K' distance from each other, otherwise, print "false".

Result for each 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 <= 10
1 <= N <= 10^5
1 <= K <= 10^5
-10^9 <= arr[i] <= 10^9

Time Limit: 1sec

Accepted Answer

Brute Force

The naive approach is to run two loops, the outer loop will pick each element one by one.

The inner loop compares all elements which are within ‘K’ distance from and with the currently selected element.

If the selected element matches with any of the elements that we are comparing in the inner loop then it means there is a duplicate.

Space Complexity: O(1)Explanation:

O(1)

Constant extra space is used.

Time Complexity: OtherExplanation:

O(K*N) per test case, where N is the size of the array and K is distance.

In the worst case, for each element in the array (O(N)), we will be checking the subarray of K elements (O(K)). Thus a total of O(N * K) time.

Accepted Answer

Using Map

We need to check if the duplicate exists at a distance of ‘K’.

We can do that by storing the element and its index in a map ‘MP’.
Now iterate over the array, if ‘ARR[i]’ doesn't exist in the map, then add ‘ARR[i]’ and ‘i’ in the map.
If ‘ARR[i]’ exists in the map then:
If ‘i’ - ‘MP['ARR[i]']’ is less than equal to ‘K’, then return true. As the distance of the last occurrence of ‘ARR[i]’ is less ‘K’.
Else update ‘MP[’ARR[i]']' by ‘i’. (Updating last occurrence index of ‘ARR[i]’.
Return false in all other case.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the array.

In the worst case we have to store all elements in the map,So the overall space complexity will be O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the array.

Since we are iterating over the whole array once, So the overall time complexity will be O(N).

Accepted Answer

Sliding Window Technique

We can use the sliding window technique. The idea is to process every window of size ‘K’ one at a time and store it into Set, now if the element is repeated in a window of size ‘K’ then we can say there is a duplicate within ‘K’ distance.

Initially, our window will contain the first ‘K’ element which is stored in Set.
Then for each remaining element, If it is already in the window return true. Otherwise, add it to the window. While adding the element in the window we have to also remove (i- ‘K’ - 1)^th element from the current window i.e our Set.

Space Complexity: O(1)Explanation:

O(K)

Since we are only using the set for storing a window of size ‘K’ only.So the overall space complexity will be O(K).

Time Complexity: O(n)Explanation:

O(N) per test case, where N is the size of the array.

Since we are only traversing the array once. So overall time complexity will be O(N).

Given an array 'arr' of 'N' integers and an integer 'K'. The array 'arr' may contain duplicate integers. Return "true" if the array contains any duplicate element within the 'K' distance from each other, otherwise, return "false".

Input format :

Output format :

Note

Constraints :

Top Wipro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Wipro Software Developer