Given two sorted arrays and a number x, find the pair whose sum is closest to x and the pair has an element from each array.
We are given two arrays ar1[0…m-1] and ar2[0..n-1] and a number x, we need to find the pair ar1[i] + ar2[j] such that absolute value of (ar1[i] + ar2[j] – x) is minimum.
Example:
Input: ar1[] = {1, 4, 5, 7};
ar2[] = {10, 20, 30, 40};
x = 32
Output: 1 and 30
Input: ar1[] = {1, 4, 5, 7};
ar2[] = {10, 20, 30, 40};
x = 50
Output: 7 and 40
We strongly recommend to minimize your browser and try this yourself first.
A Simple Solution is to run two loops. The outer loop considers every element of first array and inner loop checks for the pair in second array. We keep track of minimum difference between ar1[i] + ar2[j] and x.
We can do it in O(n) time using following steps.
1) Merge given two arrays into an auxiliary array of size m+n using merge process of merge sort. While merging keep another boolean array of size m+n to indicate whether the current element in merged array is from ar1[] or ar2[].
2) Consider the merged array and use the linear time algorithm to find the pair with sum closest to x. One extra thing we need to consider only those pairs which have one element from ar1[] and other from ar2[], we use the boolean array for this purpose.
[ad type=”banner”]Can we do it in a single pass and O(1) extra space?
The idea is to start from left side of one array and right side of another array, and use the algorithm same as step 2 of above approach. Following is detailed algorithm.
1) Initialize a variable diff as infinite (Diff is used to store the
difference between pair and x). We need to find the minimum diff.
2) Initialize two index variables l and r in the given sorted array.
(a) Initialize first to the leftmost index in ar1: l = 0
(b) Initialize second the rightmost index in ar2: r = n-1
3) Loop while l < m and r >= 0
(a) If abs(ar1[l] + ar2[r] - sum) < diff then
update diff and result
(b) Else if(ar1[l] + ar2[r] < sum ) then l++
(c) Else r--
4) Print the result.
Following is JAVA implementation of this approach.
[pastacode lang=”java” manual=”%2F%2F%20Java%20program%20to%20find%20closest%20pair%20in%20an%20array%0Aclass%20ClosestPair%0A%7B%0A%20%20%20%20%2F%2F%20ar1%5B0..m-1%5D%20and%20ar2%5B0..n-1%5D%20are%20two%20given%20sorted%0A%20%20%20%20%2F%2F%20arrays%2F%20and%20x%20is%20given%20number.%20This%20function%20prints%0A%20%20%20%20%2F%2F%20the%20pair%20from%20both%20arrays%20such%20that%20the%20sum%20of%20the%0A%20%20%20%20%2F%2F%20pair%20is%20closest%20to%20x.%0A%20%20%20%20void%20printClosest(int%20ar1%5B%5D%2C%20int%20ar2%5B%5D%2C%20int%20m%2C%20int%20n%2C%20int%20x)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Initialize%20the%20diff%20between%20pair%20sum%20and%20x.%0A%20%20%20%20%20%20%20%20int%20diff%20%3D%20Integer.MAX_VALUE%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20res_l%20and%20res_r%20are%20result%20indexes%20from%20ar1%5B%5D%20and%20ar2%5B%5D%0A%20%20%20%20%20%20%20%20%2F%2F%20respectively%0A%20%20%20%20%20%20%20%20int%20res_l%20%3D%200%2C%20res_r%20%3D%200%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Start%20from%20left%20side%20of%20ar1%5B%5D%20and%20right%20side%20of%20ar2%5B%5D%0A%20%20%20%20%20%20%20%20int%20l%20%3D%200%2C%20r%20%3D%20n-1%3B%0A%20%20%20%20%20%20%20%20while%20(l%3Cm%20%26%26%20r%3E%3D0)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20this%20pair%20is%20closer%20to%20x%20than%20the%20previously%0A%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20found%20closest%2C%20then%20update%20res_l%2C%20res_r%20and%20diff%0A%20%20%20%20%20%20%20%20%20%20%20if%20(Math.abs(ar1%5Bl%5D%20%2B%20ar2%5Br%5D%20-%20x)%20%3C%20diff)%0A%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res_l%20%3D%20l%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20res_r%20%3D%20r%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20diff%20%3D%20Math.abs(ar1%5Bl%5D%20%2B%20ar2%5Br%5D%20-%20x)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20If%20sum%20of%20this%20pair%20is%20more%20than%20x%2C%20move%20to%20smaller%0A%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20side%0A%20%20%20%20%20%20%20%20%20%20%20if%20(ar1%5Bl%5D%20%2B%20ar2%5Br%5D%20%3E%20x)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20r–%3B%0A%20%20%20%20%20%20%20%20%20%20%20else%20%20%2F%2F%20move%20to%20the%20greater%20side%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20l%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Print%20the%20result%0A%20%20%20%20%20%20%20%20System.out.print(%22The%20closest%20pair%20is%20%5B%22%20%2B%20ar1%5Bres_l%5D%20%2B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%22%2C%20%22%20%2B%20ar2%5Bres_r%5D%20%2B%20%22%5D%22)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20program%20to%20test%20above%20functions%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20ClosestPair%20ob%20%3D%20new%20ClosestPair()%3B%0A%20%20%20%20%20%20%20%20int%20ar1%5B%5D%20%3D%20%7B1%2C%204%2C%205%2C%207%7D%3B%0A%20%20%20%20%20%20%20%20int%20ar2%5B%5D%20%3D%20%7B10%2C%2020%2C%2030%2C%2040%7D%3B%0A%20%20%20%20%20%20%20%20int%20m%20%3D%20ar1.length%3B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20ar2.length%3B%0A%20%20%20%20%20%20%20%20int%20x%20%3D%2038%3B%0A%20%20%20%20%20%20%20%20ob.printClosest(ar1%2C%20ar2%2C%20m%2C%20n%2C%20x)%3B%0A%20%20%20%20%7D%0A%7D” message=”JAVA” highlight=”” provider=”manual”/] [ad type=”banner”]