Last Updated: 4 Apr, 2021
Contains Duplicate lll
Moderate
Asked in companies
You are given an integer array 'ARR' of size ‘N’ and two integers ‘A’ and ‘B’. You need to find if there are two distinct indices in the array, such that the absolute difference of values on those indices is less than or equal to ‘B’ and the absolute difference of the indices is less than or equal to ‘A’.
Note :
Can you try to solve it in O(N) time ?
Input Format :
The first line contains an integer ‘T’ which denotes the number of test cases or queries to be run. Then the test cases are as follows.
The first line of each test case contains three space-separated integers ‘N’, ‘A’ and ‘B’, denoting the number of elements in the array, and the two integers.
The next line contains 'N' space-separated integers denoting an array of ‘N’ elements.
Output Format :
For each test case, print "True" if a pair of distinct indices satisfying the above conditions exist in the given array. Otherwise, print "False".
Print the output of each test case in a separate line.
Note :
You don’t need to print anything; It has already been taken care of.
Constraints :
1 <= T <= 100
1 <= N <= 10^4
1 <= A <= 10^4
0 <= B <= 10^9
-10^9 <= ARR[i] <= 10^9
Where ‘T’ is the number of test cases, ‘N’, denotes the number of elements in the array, ‘A’ and ‘B’ denotes the given two integers, and 'ARR[i]' denotes the 'i'th' element of the array 'ARR'.
Time limit: 1 sec
Approaches
Approach: The basic approach to this question will be to simply use two loops and check for each possible pair of indices if it follows the given rule or not.
Algorithm:
- Outer loop: 0 to N - 1, and inner loop: outer + 1 to N - 1
- Check if abs(arr[outer] - arr[inner]) <= B, and abs(outer - inner) <= A. If the above conditions hold, then we will return True.
- If we have not returned True till now, this means that no such pair of indices exist. Therefore, we will return False.
Approach: In this approach, we will try to maintain a window of size ‘A’, of the previous values that can be queried for the value ranges. We will use a multiset to maintain the window of size ‘A’.
Algorithm:
- Traverse through the numbers of the array
- Maintain a multiset of size ‘A’.
- Subtract ‘B’ from arr[i] and find its lower_bound in the multiset.
- If the lower_bound is found in the multiset and the difference is less than or equal to ‘B’, then we will return True.
- Insert arr[i] into the multiset for future calculations and delete the value at index i - A from the multiset.
- If we have not returned True till now, this means that no such pair of indices exist. Therefore, we will return False.
Approach: In this approach, we will use the concept of sliding windows and buckets together to optimize the solution.
Sliding window will ensure that only those indices are considered whose absolute difference is at most ‘A’. We only consider ‘A’ indices at a time. This fulfils the second condition.
Buckets will be used to ensure that the absolute difference between two numbers is at most ‘B’. We will be dividing each number by ‘B + 1’ and put it in a bucket with its key as the quotient.
Let us understand this with the help of an example:
Let array : [1, 5, 2, 4, 3, 9, 1, 5, 9], A = 2 and B = 3
We will divide each number of the array with ‘B + 1’ and put them into buckets accordingly.
Bucket[0] will contain numbers 0, 1, 2, 3, whichever present in the array.
Bucket[1] will contain numbers 4, 5, 6, 7, whichever present in the array.
Bucket[2] will contain numbers 8, 9, 10, 11, whichever present in the array.On observing the buckets, we can see that the absolute difference between any two numbers in any bucket is at most ‘B’, which is what we want.
Also, there can be a case where the neighbouring bucket has some number whose absolute difference with a number in the current bucket is at most ‘A’. For instance, 2 lies in Bucket[0] and 4 lies in Bucket[1] and 4 - 2 = 2 < 3 (= A). This can only happen in neighbouring buckets. Therefore, we need to check for this bucket too.
Algorithm:
- Create a HashMap “buckets”
- Add numbers of the array into the buckets by dividing them with ‘B + 1’
- The base case would be that if the bucket having size greater than 1 already exists, then it is guaranteed that an answer exists. So, we will return True.
- Else, we will iterate through the buckets in order of their quotient values:
- Compare the minimum element of the current bucket to the maximum element of the last bucket.
- If we have not returned True till now, this means that no such pair of indices exist. Therefore, we will return False.