# Closest Pair in Sorted Array

## Closest Pair in Sorted Array

In the closest pair in sorted array problem, we have to find a pair of elements in the array such that the sum of these elements is nearest to the given value. It is a famous problem asked in many interviews. 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 Sorted Array Problem Description

Given a sorted array of n integers and a value x. Find the pair of elements from the array such that the sum of the elements is closest to the given value x.

Input:

• First-line contains two integers n & x.
• The next Line contains n integers the elements of the array.

Output:

• The required pair.

Example

Input

• 3 4
• 2 3 5

Output

• 2 3

Explanation

The possible pair are –

• 2 & 3
• 2 & 5
• 3 & 5

Out of all these pairs 2 & 3 has closest sum to given value 4.

## Closest Pair in Sorted Array 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(n^2)

Space Complexity – O(1)

### Optimized Approach

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

• L points to the beginning of the array.
• R points to the end of the array.

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

Time Complexity – O(n)

Space Complexity – O(1)

### Code

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

while (L < R)
{
int cur = abs(arr[L] + arr[R] – sum);
if (cur < difference)
{
difference = cur;
p = {arr[L], arr[R]};
}

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

cout << “The required pair is – “;
cout << p.first << ” “ << p.second << endl;
}
int main()
{
int n = 6x = 43;
int arr[] = {102528394049};
printPair(arrnx);
return 0;
}

### Output

`The required pair is - 10 28`