# Closest Pair in Two Sorted Arrays

## 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 n1int n2int sum)
{
pair<intintp;
p = {-1, –1};
int difference = INT_MAX;
int L = 0R = 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 = 6x = 43;
int A1[] = {102528394049};

int n2 = 5;
int A2[] = {47102029};

printPair(A1A2n1n2x);
return 0;
}

### Output

`The required pair is -> 39 4`