Last Updated: 19 Dec, 2020
Contains Almost Duplicate
Easy
Asked in company
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’.
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
Approaches
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:
- If | i - j | <= ‘K’ and | ARR[i] - ARR[j] | <= ‘L’, then return True.
- Else, return False.
The basic idea of this approach is to use an ordered_map to store the index of the elements of the array/list so that we can very easily find if the lower/upper bound of a particular element exist or not. So we will maintain an ordered_map which will contain elements such that the difference between the largest and smallest index is less than ‘K’.
Let us start traversing the given array/list and assume that we are currently at j-th index and we are trying to find an element with index ‘i’ such that pair (i, j) satisfies the condition given in the problem statement. Now we need to check if there is an element at any index ‘i’ such that ‘j’ - ‘K’ <= ‘i’ < ’j’ and ARR[j] - ‘L’ <= ARR[i] <= ARR[j] + ‘L’. Since we are maintaining a sliding window of ordered_map which contains all the elements of subarray [j - ‘K’, ‘j’ - ’1’] we can easily find if an element within a particular range exists or not.
Consider the following steps :
- Create a ordered_map<int,int> indexOfElement (in C++) which stores the pair of <element, index>.
- Start traversing the array/list using a variable ‘j’ such that 0 <= ‘j’ <= ‘N’ - 1
- At each iteration, find the index of the smallest element in the window which is greater than or equal to (ARR[j] - ‘L’) and store it in a variable ‘i’.
- If it exists, then check whether the pair (i, j) satisfies the condition specified in the problem statement, i.e. | ARR[i] - ARR[j] | <= ‘L’
- If it does, then return True.
- If it exists, then check whether the pair (i, j) satisfies the condition specified in the problem statement, i.e. | ARR[i] - ARR[j] | <= ‘L’
- Remove the element at (i - k)-th index because we will be sliding the window one step towards the right.
- Add the current element (i.e. ARR[j]) in the window.