Problem solving with programming: Minimum difference between two sorted arrays
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.
Read full article from Problem solving with programming: Minimum difference between two sorted arrays
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.
- 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.
You have two arrays of integers, where the integers do not repeat and the two arrays have no common integers.
Let x be any integer in the first array, y any integer in the second. Find min(Abs(x-y)). That is, find the smallest difference between any of the integers in the two arrays.
Assumptions: Assume both arrays are sorted in ascending order.
public static int minAbs(int[] a, int[] b) { if (a == null || b == null || a.length == 0 || b.length == 0) { return -1; } int i = 0, j = 0; int minAbs = Integer.MAX_VALUE; while (i < a.length && j < b.length) { if (a[i] < b[j]) { minAbs = Math.min(minAbs, b[j] - a[i]); ++i; } else if (a[i] > b[j]){ minAbs = Math.min(minAbs, a[i] - b[j]); ++j; } else { // cannot be smaller minAbs = 0; break; } } return minAbs; }
http://www.zrzahid.com/smallest-difference-between-2-elements-from-2-different-array/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++;elsei++;}if( i < array1.length ) //array1 has some more elements{j--; // j has reached the end, move it to last elementwhile ( 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;}
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.
It’ll be O(n^2) as we need to iterate the 2nd list for each element of 1st list.
Approach 2: with sorting
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; }http://www.jiuzhang.com/qa/669/
Read full article from Problem solving with programming: Minimum difference between two sorted arrays