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.

Have you met this question in a real interview? 

Yes

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) {

        // write your code here

        Arrays.sort(A);

        Arrays.sort(B);

        

        int pA = 0, pB = 0, minDiff = Integer.MAX_VALUE;

        

        while(pA < A.length && pB < B.length){

            minDiff = Math.min(minDiff, Math.abs(A[pA] - B[pB]));

            if(A[pA] > B[pB]) pB++;

            else pA++;

        }

        return minDiff;

    }

}