# The Smallest Difference

## Question

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

Tags

Two Pointers LintCode Copyright Sort Array

## Analysis

Brutal Force 双重for循环，找Math.abs(A[i] - B[j])的最小值

1. 再通过二分查找O(logn)，在B[j]中找接近A[i]的元素，找n次，总共时间复杂度O(n * logn)

2. two pointers，只要A[i] < B[j]，那么i++；反之，j++，循环结束条件就是i, j有一者达到数组边界

``````A = [3,6,7,4]
B = [2,8,9,3]
``````

``````A = [3,4,6,7]
B = [2,3,8,9]
``````

## Solution

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

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

int i = 0, j = 0;
int minDiff = Integer.MAX_VALUE;
while (i < A.length && j < B.length) {
minDiff = Math.min(Math.abs(A[i] - B[j]), minDiff);
if (A[i] < B[j]) {
i++;
} else {
j++;
}
}
return minDiff;
}
}
``````