Closest sum

Closest sum_pair

From Youtuber: CS Dojo

Closest sum_pair

1. Problem Statement

given two arrays and a target value, we need to find the pair value that their sum is most closest to the target value.

2. Analysis

solution 1, brute force

check every pair and compare the sum with the target value.(time: O(n^2))
solution 2, traverse one array, for every element in this array, check if b = (target-ele) occurs in another array, this will cost O(n) in time; if no pair that their sum is equal to target, find the let the target1 = target-1, then repeat the former steps, if no pair, then let the target2 = target +1, then repeat the same steps; this will cost O(x*n) time, x is the difference between the result sum between the target value.

3. Solution.

Sort the two arrays firstly, generate a matrix in which the x-axis is the sorted array a, the y-axis is the sorted array b, then use binary search to find the optimal value. O(nlogn) time complexity and O(n) space complexity.

4. Java code

 1 public static int[] closestSumPair(int[] a1, int[] a2, int target) {
 2         int[] a1Sorted = Arrays.copyOf(a1, a1.length);
 3         Arrays.sort(a1Sorted);
 4         int[] a2Sorted = Arrays.copyOf(a2, a2.length);
 5         Arrays.sort(a2Sorted);
 6 
 7         int i = 0;
 8         int j = a2Sorted.length - 1;
 9         int smallestDiff = Math.abs(a1Sorted[0] + a2Sorted[0] - target);
10         int[] closestPair = {a1Sorted[0], a2Sorted[0]};
11 
12         while (i < a1Sorted.length && j >= 0 ) {
13             int v1 = a1Sorted[i];
14             int v2 = a2Sorted[j];
15             int currentDiff = v1 + v2 - target;
16             if (Math.abs(currentDiff) < smallestDiff) {
17                 smallestDiff = Math.abs(currentDiff);
18                 closestPair[0] = v1; closestPair[1] = v2;
19             }
20 
21             if (currentDiff == 0) {
22                 return closestPair;
23             }
24             else if (currentDiff < 0) {
25                 i += 1;
26             }
27             else {
28                 j -= 1;
29             }
30         }
31 
32         return closestPair;
33     }
34 }

5. Python Code

 1 def closest_sum_pair(a1, a2, target):
 2     a1_sorted = sorted(a1)
 3     a2_sorted = sorted(a2)
 4     i = 0
 5     j = len(a2_sorted) - 1
 6     smallest_diff = abs(a1_sorted[0] + a2_sorted[0] - target)
 7     closest_pair = (a1_sorted[0], a2_sorted[0])
 8     while i < len(a1_sorted) and j >= 0:
 9         v1 = a1_sorted[i]
10         v2 = a2_sorted[j]
11         current_diff = v1 + v2 - target
12         if abs(current_diff) < smallest_diff:
13             smallest_diff = abs(current_diff)
14             closest_pair = (v1, v2)
15 
16         if current_diff == 0:
17             return closest_pair
18         elif current_diff < 0:
19             i += 1
20         else:
21             j -= 1
22     return closest_pair