[GFG POTD Solved] Find the Closest Pair from Two Sorted Arrays 
Find the Closest Pair from Two Sorted Arrays
Finding the closest pair of elements from two sorted arrays when given a target sum is a common problem in computer science and is often encountered in various algorithmic scenarios. In this article, we will discuss the problem, understand its intuition, and present an optimized solution using Python.
Introduction
Given two sorted arrays, arr1 and arr2, along with a target sum x, the task is to find a pair of elements, one from each array, whose sum is closest to the given target sum x. If there are multiple pairs with the same closest difference, any one of them can be returned.
For instance, consider the example where arr1 = [1, 4, 5, 7], arr2 = [10, 20, 30, 40], and x = 32. The closest pair in this case would be (1, 30) with a sum of 31, which is the closest possible to 32.
Intuition
The intuition behind this problem is to start with the first element of the first array and the last element of the second array. Calculate the sum of these two elements and track the difference between this sum and the target sum x. Move the pointers inwards while adjusting the pair to minimize this difference. By doing so, we can efficiently find the closest pair.
Approach
We can solve this problem using a twopointer approach. Here's how it works:

Initialize two pointers, left_idx and right_idx, to the first element of arr1 and the last element of arr2, respectively.

Initialize a variable diff to positive infinity to keep track of the minimum difference found so far.

Initialize closest_pair as None.

Start a loop until left_idx is less than size1 and right_idx is greater than or equal to 0.

Calculate the current sum as arr1[left_idx] + arr2[right_idx].

Calculate the current difference as abs(current_sum  target_sum).

If the current difference is less than diff, update diff and closest_pair accordingly.

Move the pointers based on the comparison of the current sum with the target sum
 If the current sum is less than the target sum, increment left_idx.
 Otherwise, decrement right_idx.
 Once the loop ends, return closest_pair, which will be the closest pair with the minimum difference.
Optimized Code
Let's implement the optimized code for this problem:
class Solution:
def printClosest(self, arr1, arr2, size1, size2, target_sum):
diff = float("inf")
left_idx, right_idx = 0, size21
closest_pair = None
while left_idx < size1 and right_idx >= 0:
current_sum = arr1[left_idx] + arr2[right_idx]
current_diff = abs(current_sum  target_sum)
if current_diff < diff:
diff, closest_pair = current_diff, [arr1[left_idx], arr2[right_idx]]
if current_sum < target_sum:
left_idx += 1
else:
right_idx = 1
return closest_pair
Dry Run Example
Let's dry run the code using the provided example:
arr1 = [1, 4, 5, 7]
arr2 = [10, 20, 30, 40]
size1 = 4
size2 = 4
target_sum = 32
 Calculate current_sum as 1 + 40 = 41.
 Calculate current_diff as abs(41  32) = 9.
 Update diff to 9 and closest_pair to [1, 40].
 Since current_sum is greater than target_sum, decrement right_idx to 2.
 Calculate current_sum as 1 + 30 = 31.
 Calculate current_diff as abs(31  32) = 1.
 Update diff to 1 and closest_pair to [1, 30].
 Since current_sum is less than target_sum, increment left_idx to 1.
 Calculate current_sum as 4 + 30 = 34.
 Calculate current_diff as abs(34  32) = 2.
 No update to diff or closest_pair as the difference is not smaller.
 Since current_sum is greater than target_sum, decrement right_idx to 1.
 Calculate current_sum as 4 + 20 = 24.
 Calculate current_diff as abs(24  32) = 8.
 No update to diff or closest_pair as the difference is not smaller.
 Since current_sum is less than target_sum, increment left_idx to 2.
 Calculate current_sum as 5 + 20 = 25.
 Calculate current_diff as abs(25  32) = 7.
 No update to diff or closest_pair as the difference is not smaller.
 Since current_sum is less than target_sum, increment left_idx to 3.
 Calculate current_sum as 7 + 20 = 27.
 Calculate current_diff as abs(27  32) = 5.
 No update to diff or closest_pair as the difference is not smaller.
 Since current_sum is less than target_sum, increment left_idx to 4.
 The loop ends as left_idx is now equal to 4.
Representative Image 
The function returns 1 as the minimum difference to the target sum 31.
Time and Space Complexity
 Time Complexity: The time complexity of this algorithm is O(max(size1, size2)) since we iterate through both sorted arrays once.
 Space Complexity: The space complexity is O(1) as we use a constant amount of extra space for variables.
Conclusion
In this article, we discussed the problem of finding the closest pair from two sorted arrays with a target sum. We provided an efficient solution using a twopointer approach, which allows us to find the closest pair in linear time complexity. This algorithm can be useful in scenarios where you need to find the most suitable pair of elements from two sorted arrays based on their sum.
KeyWords & Tags
 gfg potd solution today
 Gfg potd solution java
 Gfg potd solution example
 Gfg potd solution github
 gfg potd solution python
 dfs of graph gfg potd solution
 adding ones gfg potd solution
 arranging the array gfg potd solution