[GFG POTD Solved] Find the Closest Pair from Two Sorted Arrays | GeeksforGeeks | September 27 2023

[GFG POTD Solved] Find the Closest Pair from Two Sorted Arrays

Posted Originally by Author :- https://auth.geeksforgeeks.org/user/gevendraverma45/

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 two-pointer approach. Here's how it works:

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

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

3. Initialize closest_pair as None.

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

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

6. Calculate the current difference as abs(current_sum - target_sum).

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

8. 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.

9. 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, size2-1
        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

Initialize left_idx to 0 and right_idx to 3.

Iteration 1:

• 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.

Iteration 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.

Iteration 3:

• 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.

Iteration 4:

• 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.

Iteration 5:

• 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.

Iteration 6:

• 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 two-pointer 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