Last Updated: 19 Dec, 2020
Contains Duplicate ll
Easy
Asked in companies
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
Approaches
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:
- 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.
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<element, index>. 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
- 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.