Scribble 5: Smallest Difference

Here’s the problem statement:
Given two arrays of integers, find a pair of integers – one from each array such that the length of the real number line between them is the smallest.

Assume there is only one such pair.

For example:
Array1: 1, 11, 15, 2
Array2: 500, 23, 19, 127, 12, 4
Output: 1 (difference between the values 11 and 12)

Let’s dive into the solution: Here are 2 approaches to solve this problem:

Approach 1:

Run a doubly nested loop to generate all pairs possible using one value from array 1 and another from array 2. Find the difference between the 2 values in each pair and return the minimum difference thus possible.

Time complexity: O(N²) since we use a doubly nested loop

Space complexity: O(1)

Here’s the code for the above solution in java:

public int[] smallestDifference(int[] array1, int[] array2) {
	int val1, val2, diff;
	val1 = val2 = diff = 0;
	int minDiff = Integer.MAX_VALUE;
	for(int i =0;i<array1.length;i++) {
		for(int j=0;j<array2.length;j++) {
			{
				 	diff = Math.abs(array1[i]-array2[j]);
					if(diff == 0)//we've found the minimum possible difference so we can just return
						return new int[]{array1[i], array2[j]};
					if(diff<minDiff) {
						minDiff = diff;
						val1 = array1[i];
						val2 = array2[j];
					}
			}
		}
	}
	return new int[] {val1, val2};
}

Approach 2:

Sort both the arrays first and then set two pointers i, j to iterate through the first and the second arrays respectively:

begin with i = j = 0,
calculate difference between array1[i] and array2[j]
update the minimumDifference if needed
if (array[i]1<array2[j]): then increment i hoping that array1[i+1] will be closer to array2[j] than array1[i]. (Note in this case we don’t increment j instead because that’ll mean an increase in difference as array[j+1]>array[j] since the array is sorted in ascending order.)
else: increment j

repeat steps 2 to 4 while i and j are not at the ends of their arrays.

Time complexity: Let m, n be the lengths of the 2 arrays.
O(nlogn + mlogm) is the time needed for sorting the two arrays .
Going over both the arrays using i, j takes O(m+n) time (as using the two pointers we totally go over m+n number of elements).
Therefore the overall time complexity is: O(nlogn + mlogm)

Space complexity: O(1)

Here’s the code for the above solution in java:

public int[] smallestDifference(int[] array1, int[] array2) {

	Arrays.sort(array1);
	Arrays.sort(array2);
	int minDiff = Integer.MAX_VALUE;
	int val1, val2, diff, i, j;
	val1 = val2 = diff = i = j = 0;	
	
	while(i<array1[i].length && j< array2.length){
			diff = Math.abs(array1[i]-array2[j]); 
			if(diff==0)//we've found the minimum possible difference so we can just return
				return new int[]{array1[i], array2[j]};
			if(diff<minDiff) {
				minDiff = diff;
				val1 = array1[i]; 
				val2 = array2[j];
			}
			if(array1[i]<array2[j]) 
				i++;
			else
				j++;
	}
	return new int[] {val1, val2};
}

Please do let me know if you find this article useful. Also, it’ll be great if you’d provide some feedback. To reach out, please leave a comment in the Contact section. Thanks! Happy Coding! 🙂

Share this:

Related