Problem

Submissions

Hints & solutions

Discuss

Contains Duplicate lll

Moderate

0/80

Average time to solve is 10m

Contributed by

3 upvotes

Asked in companies

Problem statement

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 ?

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

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

Sample Input 1 :

Sample Output 1 :

True
False

Explanation Of Sample Input 1 :

In the first test case, 
For indices 0 and 3, abs(0 - 3) = 3, which is equal to A and values at those indices 2 and 2, abs(2 - 2) = 0, which is equal to B, hence the answer is True in this case.
In the second test case, 
There exist no pair of indices satisfying the above conditions, hence the answer is False in this case.

Sample Input 2 :

2
4 1 2
2 1 2 2
6 2 3
2 6 10 2 6 10

Sample Output 2 :

True 
False

Hint 1

Hint 2

Hint 3

Can you think of checking each pair of indices one by one?

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

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.

Time Complexity

O(N^2), where N is the number of elements in the array.

Since we are traversing through the complete array using two loops. Hence, the overall Time complexity is O(N^2).

Space Complexity

O(1).

Constant extra space is required. Hence, the overall Space Complexity is O(1).

(100% EXP penalty)

Contains Duplicate lll

Console