Smallest Difference between 2 elements from 2 different array

Given two arrays. Find the smallest difference between two elements from both of the arrays.

For example: A=[0, -6, 4, 6, 5, -2], and A=[-4, 8, 2, 3, 10, 9] then then the smallest difference between two elements of the two array is 1 with pairs (4, 3) from the arrays repectively.

Approach 1: w/o sorting
It’ll be O(n^2) as we need to iterate the 2nd list for each element of 1st list.

Approach 2: with sorting
Observe that consecutive elements in a sorted array must be of minimum difference a among any of non-consecutive pairs. So, for finding minimum difference pair in a singe array we would sort the array and find the minimum difference consecutive pair of elements.

For example, after sorting A = [-5, -2, 0, 4, 5, 6]. Then (4, 5) and (5, 6) is the minimum difference pair.

In order to find min diff among two sorted we need to do extend this approach.

1. Sort the arrays with O(nlgn), n is the size of larger array.
2. Keep 2 pointers to point the start of the sorted arrays.
3. Find difference between the elements pointed by the two points. If this is less then minimum difference so far then update the min diff and also update the min diff pairs.
4. In order to progress the algorithm we move to right of array which has a smaller element in the current pointer. This is due to the fact that the arrays are sorted in ascending order. So, if a pointer has smaller element then the other then we can move forward the smaller pointer to right with the hope that we get a larger element that will make smaller difference with the other pointer.

Below is the implementation of the above idea. Total time complexity: O(nlgn)+O(n) = O(nlgn)

public static int minDiffElements(int a1[], int a2[]){
	int minDiff = Integer.MAX_VALUE;
	int min1 = -1;
	int min2 = -1;
	int i = 0;
	int j = 0;
	int n1 = a1.length;
	int n2 = a2.length;
	int diff = 0;
	
	Arrays.sort(a1);
	Arrays.sort(a2);
	while(i < n1 && j < n2){
		diff = Math.abs(a1[i]-a2[j]);
		if(diff < minDiff){
			minDiff = diff;
			min1 = a1[i];
			min2 = a2[j];
		}
		
		if(a1[i] < a2[j]){
			i++;
		}
		else{
			j++;
		}
	}
	
	System.out.println("min diff between two array elements: between "+min1+" and "+min2+" min diff: "+minDiff);
	return minDiff;
}