Three Pointer.

Moderate
0/80
Average time to solve is 15m
43 upvotes
Asked in companies
Cerner CorporationGoogle inc

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
1
5
1 2 3 4 5
5
1 3 5 7 9
3
2 4 6
Sample Output 1:
1
Explanation for Sample Input 1:
For firstestcase :
One of the possible answer is choose i = 0, j = 0 and k = 1.
Thus it will 1 answer.
Sample Input 2:
1
4
1 1 1 1
4
2 2 2 2
5
7 7 7 7 7
Sample Output 2:
6
Hint

Try the simplest possible way.

Approaches (2)
Try the simplest possible way.
  • 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.
Time Complexity

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

Space Complexity

O(1), as we are using constant extra memory.

Code Solution
(100% EXP penalty)
Three Pointer.
Full screen
Console