Contains Duplicate ll

Easy

0/40

Average time to solve is 15m

6 upvotes

Asked in companies

Problem statement

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’.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

2
6 3
1 2 4 3 4 5
4 2
5 4 7 6

Sample Output 1 :

Yes
No

Explanation of sample input 1 :

In the first test case, consider (2, 4) a pair of distinct indices where ARR[2] = ARR[4] and |2 - 4| = 2 which is less than or equal to ‘K’. So print “Yes”.

In the second test case, each element of the given array is distinct. So print “No”.

Sample Input 2 :

Sample Output 2 :

Yes
No

Explanation for sample input 2 :

In the first test case, consider (0, 1) a pair of distinct indices where ARR[0] = ARR[1] and |0 - 1| = 1 which is less than or equal to ‘K’. So print “Yes”.

In the second test case, each element of the given array is distinct. So print “No”.

Hint 1

Hint 2

Can you think of considering all pairs of elements?

Approaches (2)

Approach 1

Approach 2

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.

Time Complexity

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).

Space Complexity

O(1)

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

(100% EXP penalty)

Contains Duplicate ll

Console