Pair Difference K

PROBLEM STATEMENT

You are given a sorted array ARR of integers of size N and an integer K. You have to find whether it is possible to find a pair of integers having an absolute difference of K.

Note:

1. K is a non-negative integer.

2. Absolute Difference between two integers A and B is equal to the difference of maximumOf(A, B) and minimumOf(A, B).

3. Pair of integers should have different indices in the array.

Input format:

The first line of input contains an integer T, denoting the number of test cases.

The first line of each test case consists of two space-separated integers N and K, denoting the size of the given array ARR and the required absolute difference.

The second line of each test case consists of N space-separated integers denoting the elements of the array.

Output format:

For each test case print, “Yes” if it is possible to have a pair of integers having absolute difference equal to K and “No” otherwise, in a separate line.

Note:

You don't have to print anything, it has already been taken care of. Just Implement the given function.

Constraints:

1 <= T <= 100
1 <= N <= 10^4
1 <= ARR[i] <= 10^9
0 <= K <= 10^9

Time Limit: 1 sec.

Approach 1

Iterate through the array ARR (with for loop variable i), consider this as one of the possible element in pair and let’s call it A(A = ARR[i]).
For each element A, iterate through the array ARR(with for loop variable j), consider this as the possible other element in the pair along with A. And let’s call it B(B = ARR[j]). But if i is equal to j then you cannot make this pair, hence move forward and try other pairs.
If the absolute difference between A and B (|A-B|), is equal to K, then we get the required pair and we can print “Yes”.
If after trying all possible pairs in the array we are unable to find the required pair we simply print “No”.

Try Problem

Approach 2

Make a hashmap to mark if an integer is present in the array or not.
Iterate through the elements of array ARR, and check if ARR[i] - K (for some index i) is already present in the array or not. We will not check the presence of ARR[i] + k, because the array is already sorted, hence it is impossible to find integers greater than ARR[i], before ARR[i] in the array.
If ARR[i] - K is found in the hashmap ( which also means it is present in the array as well) then we found our required pair and we print “Yes”.
If ARR[i] - K is not present in the hashmap (which also means it is absent in the array so far), hence we mark the current integer in the hashmap and move forward.
If even after traversing the whole array, the required pair is not found, we will print “No”.

Try Problem

Approach 3

As the given array is already sorted, hence we can make use of this fact to optimize time and space complexity.
We will take two pointers which will point to two integers which denote some possible pair in the array. Let’s call them i and j respectively.
So there are three possible cases for given i and j.
- If ARR[j] - ARR[i] == K, then this means we can have a pair of integers in the array whose absolute difference is equal to K.
- If ARR[j] - ARR[i] < K then this denotes the current difference between integers pointed by i and j is less than K which needs to be increased.
  - In this situation incrementing i will tend to decrease this difference because the array is already sorted, hence this won’t be a good option.
  - But incrementing j leads to an increase in the difference because the array is already sorted, hence we increment j in such condition.
- If ARR[j] - ARR[i] > K then this denotes the current difference between integers pointed by i and j is greater than K which needs to be decreased.
  - In this situation incrementing j will tend to increase this difference because the array is already sorted, hence this won’t be a good option.
  - But incrementing i leads to a decrease in the difference because the array is already sorted, hence we increment i in such condition.
If after traversing the whole array we are unable to find the required pair, then we print “No”.
One thing to make sure while checking for some pairs, i should not be equal to j.

Try Problem