Check Indices With Given Difference Problem Statement

You are provided with an integer array ARR of size N along with two integers A and B. Your task is to determine if there exist two distinct indices in the array such that the absolute difference of the values at those indices is less than or equal to B and the absolute difference of the indices is less than or equal to A.

Strive to achieve an O(N) time complexity solution.

Input:

The first line contains an integer T indicating the number of test cases or queries. The following details are provided for each test case: The first line contains three space-separated integers: N (number of elements in the array), A, and B. The second line contains N space-separated integers representing the elements of the array ARR.

Output:

For each test case, output "True" if there exists a pair of distinct indices satisfying the conditions. Otherwise, output "False". Each result should be printed on a new line for every test case.

Example:

Input: T = 1 N = 5, A = 3, B = 2 ARR = [1, 5, 7, 2, 6] Output: True

Constraints:

1 ≤ T ≤ 100

1 ≤ N ≤ 10⁴

1 ≤ A ≤ 10⁴

0 ≤ B ≤ 10⁹

-10⁹ ≤ ARR[i] ≤ 10⁹

Time limit: 1 second

Note:

No need to print anything in the function implementation as printing is handled externally.

Question

Check Indices With Given Difference Problem Statement

You are provided with an integer array ARR of size N along with two integers A and B. Your task is to determine if there exist two distinct indices in the array such that the absolute difference of the values at those indices is less than or equal to B and the absolute difference of the indices is less than or equal to A.

Strive to achieve an O(N) time complexity solution.

Input:

The first line contains an integer T indicating the number of test cases or queries. The following details are provided for each test case: 
The first line contains three space-separated integers: N (number of elements in the array), A, and B. 
The second line contains N space-separated integers representing the elements of the array ARR.

Output:

For each test case, output "True" if there exists a pair of distinct indices satisfying the conditions. Otherwise, output "False". Each result should be printed on a new line for every test case.

Example:

Input: 
T = 1 
N = 5, A = 3, B = 2 
ARR = [1, 5, 7, 2, 6] 
Output: 
True

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 10⁴
1 ≤ A ≤ 10⁴
0 ≤ B ≤ 10⁹
-10⁹ ≤ ARR[i] ≤ 10⁹
Time limit: 1 second

Note:

No need to print anything in the function implementation as printing is handled externally.

Accepted Answer

To solve the problem efficiently in 
𝑂
(
𝑁
)
O(N) time for each test case, we need to check whether there exist two distinct indices i and j in the array ARR such that:

∣
𝐴
𝑅
𝑅
[
𝑖
]
−
𝐴
𝑅
𝑅
[
𝑗
]
∣
≤
𝐵
∣ARR[i]−ARR[j]∣≤B (the absolute difference of values is less than or equal to B)
∣
𝑖
−
𝑗
∣
≤
𝐴
∣i−j∣≤A (the absolute difference of indices is less than or equal to A)
Plan:
Use a Sliding Window and Hash Set:

For each index i in the array, maintain a sliding window of size A. This window will track all the values of ARR from indices i - A to i - 1.
For each new element ARR[i], check if there exists any element in this sliding window such that the absolute difference of values is less than or equal to B.
We can efficiently check the absolute value difference condition using a sorted set (or balanced binary search tree), but since the problem constraints are large, a hash set can work well too if handled carefully.
Algorithm Steps:

For each element ARR[i], maintain a sliding window of previous A elements (i.e., indices i-1, i-2, ..., i-A).
For each new element, check the values in the window to see if any satisfies 
∣
𝐴
𝑅
𝑅
[
𝑖
]
−
𝐴
𝑅
𝑅
[
𝑗
]
∣
≤
𝐵
∣ARR[i]−ARR[j]∣≤B. If such a value exists, return True.
Update the sliding window: add the current element to the set and remove elements that are out of range of the window size A.
Efficient Checking:

As we move through the array, we will use a hash set to keep track of the values of the recent A elements.
For each new value ARR[i], iterate through the hash set and check if any existing value satisfies the condition 
∣
𝐴
𝑅
𝑅
[
𝑖
]
−
𝑥
∣
≤
𝐵
∣ARR[i]−x∣≤B. If yes, return True.
After checking, update the hash set: add the current element and remove the element that goes out of the range of A.
Python Code:
def check_indices_with_given_difference(T, test_cases):
    for test_case in test_cases:
        N, A, B, ARR = test_case
        window_set = set()  # A set to maintain the sliding window of size at most A
        
        for i in range(N):
            # Check if there is any value in the window that satisfies the condition
            for val in window_set:
                if abs(ARR[i] - val) <= B:
                    print("True")
                    break
            else:
                # Add current element to the set (continue if no break was hit)
                window_set.add(ARR[i])
                
                # Maintain the size of the sliding window to be at most A
                if i >= A:
                    window_set.remove(ARR[i - A])
                
                continue
            break
        else:
            print("False")

# Example Usage:
T = 2  # number of test cases
test_cases = [
    (5, 2, 3, [1, 2, 3, 1, 5]),  # Test case 1
    (4, 1, 0, [1, 2, 3, 4])       # Test case 2
]
check_indices_with_given_difference(T, test_cases)
Explanation:
Input Parsing:

We receive the number of test cases T. For each test case, we get N (number of elements), A (index difference), B (value difference), and the array ARR.
Sliding Window:

We use a hash set (window_set) to keep track of the previous A elements (window).
For each new element ARR[i], we check all elements in the window. If any element in the window satisfies 
∣
𝐴
𝑅
𝑅
[
𝑖
]
−
𝑣
𝑎
𝑙
∣
≤
𝐵
∣ARR[i]−val∣≤B, print "True" and move to the next test case.
Maintaining the Window:

After checking the condition, we add the current element to the set.
If the size of the set exceeds A (i.e., we are going beyond the sliding window size), we remove the element that is no longer within the last A indices.
Break and Continue:

If we find a valid pair, we use break to stop further checks and print "True". If we don't find any valid pair in the entire array, we print "False".
Complexity:
Time Complexity: 
𝑂
(
𝑁
)
O(N) for each test case, where N is the number of elements in the array.
Space Complexity: 
𝑂
(
𝐴
)
O(A) for storing the sliding window set.
This approach ensures that the solution runs efficiently even for large inputs.