Last Updated: 8 Jan, 2021
Three Pointer.
Moderate
Asked in companies
You are given three arrays X, Y and Z of size A,B and C respectively.Also, all three arrays are sorted in non-decreasing order. Find i, j, k such that : 0 <= i < A, 0 <= j < B, 0 <= k < C and max(abs(X[i] - Y[j]), abs(Y[j] - Z[k]), abs(Z[k] - X[i])) is minimized. Your task is to return the minimum of all the max(abs(X[i] - Y[j]), abs(Y[j] - Z[k]), abs(Z[k] - X[i]))
Note:
1. All the arrays are sorted in non-decreasing order.
2. abs(x) denotes the absolute value of x, i.e. if x<0, the abs function returns (-x) so that the final value of x becomes positive.
Input Format:
The first line of the input contains an integer T, denoting the number of test cases.
The first line of each test case contains the integer A, denoting the size of the X array.
The second line of each test case contains A space-separated integers denoting the array X elements.
The third line of each test case contains the integer B, denoting the size of the Y array.
The fourth line of each test case contains B space-separated integers denoting the array Y elements.
The fifth line of each test case contains the integer C, denoting the size of the Z array.
The sixth line of each test case contains C space-separated integers denoting the array Z elements.
Output Format:
For each test case, every line of output prints the minimum of the above condition.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= A,B,C <= 10^4
1 <= X[i] <= 10^4
1 <= Y[i] <= 10^4
1 <= Z[i] <= 10^4
Time Limit: 1 sec
Approaches
- The most trivial approach would be to iterate through each element of each array and check for the minimum.
- Use three loops for traversing over each array.
- Maintain a minValue variable to store the minimum value.
- After completing the iterations, return minValue.
- In this approach, we try to minimize the difference between the maximum and minimum extracted value at each index.
- We maintain three variable differences, minimum and maximum to store the current difference, minimum and maximum respectively for each index.
- We maintain 3 iterators, i,j,k pointing to the start of each array X, Y and Z respectively.
- Now, we find the values of differences, minimum and maximum for each i,j and k.
- If we found the difference at the current indices less than the previously stored difference, we update its value.
- Now, increment the pointer of the array which contains the minimum.
- We increment the pointer of the array which has the minimum because our goal is to decrease the difference.
Similar problems