Given two arrays sorted in ascending order, find the absolute minimum difference between any pair of elements |a-b| such that a is from one array and b is from another array.
For example consider the following two arrays.
array1 = [3, 27, 45, 68, 70, 81, 99]
array2 = [9, 16, 25, 35, 70, 84]
The minimum difference is 2 (27-25).
This can be calculated using the following algorithm.
- Take two indices i, j which point to the beginning of the two arrays (i.e 0)
- Take variable MinDiff and assign it the maximum possible value
- If array1[i] and array2[j] are equal return 0
- Otherwise update MinDiff if abs( array1[i] – array2[j] ) is the new minimum.
- If array1[i] > array2[j] move second index(j) forward otherwise move first index (i) forward.
- Repeat the above procedure until we reach the end of any of the two arrays.
- Finally process the remaining part of left-over array to update MinDiff.
This algorithm takes linear time – O(n) and constant space O(1). Here is the Java implementation of the above algorithm.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Created with IntelliJ IDEA. | |
| * User: Ravi | |
| * Date: 12/14/13 | |
| * Time: 7:40 AM | |
| * To change this template use File | Settings | File Templates. | |
| */ | |
| public class MinDifference { | |
| public static void main(String [] args) | |
| { | |
| int [] array1 = {12, 34, 57, 61, 69, 80}; | |
| int [] array2 = {27, 39, 48, 51, 79}; | |
| System.out.println(findMinDiff(array1,array2)); | |
| } | |
| public static int findMinDiff(int[] array1, int[] array2) | |
| { | |
| int i = 0, j = 0; | |
| int minDiff = Integer.MAX_VALUE; | |
| while ( i < array1.length && j < array2.length ) | |
| { | |
| if( array1[i] == array2[j] ) | |
| return 0; | |
| int diff = Math.abs( array1[i] - array2[j] ); | |
| minDiff = Math.min( diff, minDiff ); | |
| if( array1[i] > array2[j] ) | |
| j++; | |
| else | |
| i++; | |
| } | |
| if( i < array1.length ) //array1 has some more elements | |
| { | |
| j--; // j has reached the end, move it to last element | |
| while ( i < array1.length ) | |
| { | |
| int diff = Math.abs( array1[i] - array2[j] ); | |
| minDiff = Math.min( diff, minDiff ); | |
| i++; | |
| } | |
| } | |
| else //array2 has some more elements | |
| { | |
| i--; | |
| while ( j < array2.length ) | |
| { | |
| int diff = Math.abs( array1[i] - array2[j] ); | |
| minDiff = Math.min( diff, minDiff ); | |
| j++; | |
| } | |
| } | |
| return minDiff; | |
| } | |
| } |
by