Closest Pair in Sorted Array

November 6, 2021

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

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 n, int sum)
{
    pair<int, int> p;
    p = {-1, –1};
    int difference = INT_MAX;
    int L = 0, R = 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 = 6, x = 43;
    int arr[] = {10, 25, 28, 39, 40, 49};
    printPair(arr, n, x);
    return 0;
}

Output

The required pair is - 10 28

2 comments on “Closest Pair in Sorted Array”


  • Avothu Sharath

    import array as arr
    def closest_sum(ar,a,b):
    n = arr.array(‘i’,ar)
    d = a+b
    l1 = []
    l2 = []
    if d in n:
    print(n[n.index(d)])
    else:
    for i in range(len(n)):
    if n[i]<d:
    l1.append(n[i])
    else:
    l2.append(n[i])
    if len(l1) == 0:
    print(l2[0])
    elif len(l2) == 0:
    print(l1[-1])
    else:
    x = d-max(sorted(l1))
    y = min(sorted(l2))-d
    if x<y:
    print(max(sorted(l1)))
    else:
    print(min(sorted(l2)))
    ar = list(map(int,input("Enter a array: ").split()))
    a = int(input("Enter number1: "))
    b = int(input("Enter number2: "))
    closest_sum(ar,a,b)

    1