Contains Almost Duplicate

Easy

0/40

Average time to solve is 10m

8 upvotes

Asked in company

Problem statement

You have been given an array/list “ARR” of integers and two integers ‘K’ and ‘L’. Your task is to check if a pair of distinct indices ‘i’ and ‘j’ exist such that |ARR[i] - ARR[j]| <= ‘L’ 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 first line of each test case will contain three integers ‘N’,  ‘K’, and ‘L’ where ‘N’ is the number of elements in the array and the integers ‘K’ and ‘L’ are described 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 don’t need to print anything; It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 50
1 <= N <= 10000
0 <= K <= 10000
0 <= L <= 10^9
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 0
1 2 4 3 4 5
4 2 1
5 11 7 9

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] | <= 0 and |2 - 4| = 2 which is less than or equal to ‘K’. So print “Yes”.

In the second test case, any pair of distinct indices satisfying the constraints don’t exist. 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] | <= 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 pair 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] | <= ‘L’, then return True.
2. 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 Almost Duplicate

Console