Check Indices With Given Difference
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

Question

Check Indices With Given Difference

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

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.

Note :

Input Format :

Output Format :

Note :

Constraints :

Top IEO Makers Fablab Web Developer interview questions & answers

Popular interview questions of Web Developer