Closest Pair in Two Sorted Arrays

November 6, 2021

Closest Pair in Two Sorted Arrays

In Closest Pair in Two Sorted Arrays Problem, we have to find a pair of elements such that the sum of elements is closest sum. The problem can be optimally solved using two pointer technique. In this article we will provide a C++ solution with an explanation.

Closest Pair in Two Sorted Arrays Problem Description

Given two sorted arrays & a value x. Find a pair of elements such that –

One element of the pair belong to first array & other to the second array.
The sum of elements of the pair is closest to given value x.

Input:

First line contains single integer x.
Next line contains the size of first array.
Next Line contains n integers the elements of the first array.
First line contains a single integer the size of second array.
Next Line contains n integers the elements of the second array.

Output:

The required pair.

Closest Pair in Two Sorted Arrays Problem Solution

Brute Force

The idea here is to use two nested loops and generate all pairs. Pick the pair which has sum closest to given value x ie smallest absolute difference with x.

Time Complexity – O(n1*n2), where n1 & n2 are size of two arrays.

Space Complexity – O(1)

Optimized Approach

In optimized approach we use two pointers L & R where –

L points to the beginning of the first array.
R points to the end of the 2nd array array.

We compare the sum of A1[L] & A2[R] with the given sum – x. If it is less we increment L else we increment R.

Time Complexity – O(max(n1,n2)), where n1 & n2 are size of two arrays.

Space Complexity – O(1)

Code

#include <bits/stdc++.h>
using namespace std;
void printPair(int A1[], int A2[], int n1, int n2, int sum)
{
    pair<int, int> p;
    p = {-1, –1};
    int difference = INT_MAX;
    int L = 0, R = n2 – 1;

    while (L < n1 && R >= 0)
    {
        int cur = abs(A1[L] + A2[R] – sum);
        if (cur < difference)
        {
            difference = cur;
            p = {A1[L], A2[R]};
        }

        if (A1[L] + A2[R] < sum)
            L++;
        else
            R–;
    }

    cout << “The required pair is -> “;
    cout << p.first << ” “ << p.second << endl;
}
int main()
{
    int n1 = 6, x = 43;
    int A1[] = {10, 25, 28, 39, 40, 49};

    int n2 = 5;
    int A2[] = {4, 7, 10, 20, 29};

    printPair(A1, A2, n1, n2, x);
    return 0;
}

Output

The required pair is -> 39 4