# The Smallest Difference

LintCode-387.The Smallest Difference

Given two array of integers(the first array is array A, the second array is array B), now we are going to find a element in array A which is A[i], and another element in array B which is B[j], so that the difference between A[i] and B[j] (|A[i] - B[j]|) is as small as possible, return their smallest difference.

Example: For example, given array A = [3,6,7,4], B = [2,8,9,3], return 0

Challenge: O(n log n) time

``````public class Solution {
/**
* @param A, B: Two integer arrays.
* @return: Their smallest difference.
*/
public int smallestDifference(int[] A, int[] B) {
if (A == null || A.length == 0 || B == null || B.length == 0) {
return -1;
}

Arrays.sort(A);
Arrays.sort(B);

int diff = Math.abs(A[0] - B[0]);

for (int i = 0; i < A.length; i++) {
int low = 0, high = B.length - 1;

while (low + 1 < high) {
int middle = low + (high - low) / 2;

if (diff > Math.abs(A[i] - B[middle])) {
diff = Math.abs(A[i] - B[middle]);
}

if (A[i] == B[middle]) {
return 0;
} else if (A[i] > B[middle]) {
low = middle;
} else {
high = middle;
}
}

if (diff > Math.abs(A[i] - B[low])) {
diff = Math.abs(A[i] - B[low]);
}
if (diff > Math.abs(A[i] - B[high])) {
diff = Math.abs(A[i] - B[high]);
}
}

return diff;
}
}
``````

Here is another simpler solution.

``````public class Solution {
/**
* @param A, B: Two integer arrays.
* @return: Their smallest difference.
*/
public int smallestDifference(int[] A, int[] B) {
if (A == null || A.length == 0 || B == null || B.length == 0) {
return -1;
}

Arrays.sort(A);
Arrays.sort(B);

int diff = Math.abs(A[0] - B[0]);

int i = 0, j = 0;

while (i < A.length && j < B.length) {
diff = Math.min(diff, Math.abs(A[i] - B[j]));

if (A[i] < B[j]) {
i++;
} else {
j++;
}
}

return diff;
}
}
``````

Hope this helps,
Michael