You are given 3 arrays A, B and C. All 3 of the arrays are sorted.
Find i, j, k such that : max(abs(A[i] - B[j]), abs(B[j] - C[k]), abs(C[k] - A[i])) is minimized. Return the minimum max(abs(A[i] - B[j]), abs(B[j] - C[k]), abs(C[k] - A[i]))
**abs(x) is absolute value of x and is implemented in the following manner : **
if (x < 0) return-x;
elsereturn x;
Example :
Input :
A : [1, 4, 10]
B : [2, 15, 20]
C : [10, 12]
Output : 5
With 10 from A, 15 from B and 10 from C.
Method:
Everytime increase the index of smallest number, which will minimize the difference.
Solution:
Time: O(n) Space: O(1)
public class Solution { // DO NOT MODIFY THE LIST. IT IS READ ONLY public int minimize(final List<Integer> A, final List<Integer> B, final List<Integer> C) { int min = Integer.MAX_VALUE; int i = 0; int j = 0; int k = 0; while (i < A.size() && j < B.size() && k < C.size()) { int a = A.get(i); int b = B.get(j); int c = C.get(k); int currMax = Math.max(Math.abs(a - b), Math.max(Math.abs(a - c), Math.abs(b - c))); min = Math.min(min, currMax); if (a <= b && a <= c) { i ++; } else if (b <= a && b <= c) { j ++; } else { k ++; } } return min; } }