Challenge: Closest Target Sum in Two Sorted Arrays

Introduction

We now propose a very similar problem to the previous one. You’ll have to find a naive algorithm and implement it in both pointer and array notation. Then, you’ll have to use the two-pointers technique to implement an optimized solution.

As this is a coding challenge, you must solve it before checking the solution.

Problem statement

Given two arrays sorted in increasing order and a target number, find the pair of elements with the sum closest to the target. One is from the first array, and the other one is from the second array. As opposed to the previous problem, now the pair must contain the elements, not their indices.

In other words, find the pair ($e_{1}$, $e_{2}$), where $e_{1}$ is from arr1 and $e_{2}$ is from arr2 with the property that |$e_{1}$ + $e_{2}$ - $target$| is minimum for all possible pairs. We want the pair that sums as close as possible to target. If there’s more than one such pair, return any of them.

All values in the arrays and the target number are positive numbers or 0.

The prototype of the functions you’ll write is the following:

void solve(int arr1[], int arr2[], int arr1Size, int arr2Size, int target, int solution[])

Example input and output

Input 1:

arr1 = {0, 1, 2, 3}
arr2 = {11, 15, 22}
target = 19

Output 1:

15 3

The closest sum is 15 + 3 = 18.

The difference between the target and the sum is 19 - 18 = 1. There is no pair with a difference of less than 1.

For example, 22 + 0 = 22 - 19 = 3 > 1, this pair is not the minimum pair as we have a pair with a difference of 1.

Input 2:

arr1 = {1, 7, 9, 23}
arr2 = {13, 15, 20, 33, 44}
target = 36

Output 2:

23 13

The elements are 23 and 13. 23 + 13 = 36 which is the target. Therefore, the difference between the sum and the target is 0, and we can’t find a pair with a smaller difference.

Input 3:

arr1 = {1, 7, 9, 23}
arr2 = {13, 15, 20, 33, 44}
target = 31

Output 3:

9 20

The elements are 9 and 20.

Note: All input test cases are hidden for this challenge. Manually test with the inputs provided above. If they are not enough, come up with your own test cases.

Brute force challenge

Your task is to implement a brute-force solution. The time complexity should be $O$($n^{2}$). Use exactly two loops.

Array notation

Implement the brute-force solution in array notation.