Find the closest pair from two arrays 

By | November 28, 2021

Problem

Given two sorted arrays and an integer X, find one number from each array such that the sum of these two numbers is the lowest possible.

Approach 1

Since the arrays are sorted, we can decrement values one by one from the first array and find the remaining element in the second array. For example, if the first array is [1, 2, 3] and X is 20, then we first decrement 20 by 1, then by 2 and then by 3. In each of these, we are left with 19, 18 and 17 respectively. We then find the closest number to 19 in the second array using binary search. The closest number to decremented value is either the index at upper bound or a number at index one less than upper bound. Note that, if the upper bound is at the starting index of the array, then we don’t check the index before it. Think something similar if the upper bound is outside our array. This approach takes O(NlogN) time.

C++ Programming

#include<bits/stdc++.h>
using namespace std;
void solve(int arr[], int brr[], int n, int m, int x)
{
    
    int ans = INT_MAX;
    int sum = INT_MAX;
    int f,s;
    int xx = x;
    for(int i=0;i<n;i++){
    x-=arr[i];
    auto ind = upper_bound(brr, brr+m, x);
    int element;
    if((ind-brr)>=m) element = brr[m-1];
    else{
    if(ind!=brr){ 
    auto ind2=ind;
    ind2--;
    if(abs((brr[ind-brr]+arr[i])-xx)<=abs((brr[ind2-brr]+arr[i])-xx)) 
       element = brr[ind-brr];
    else 
       element = brr[ind2-brr];
    }
    else element = brr[ind-brr];
    }
    if(abs((element+arr[i])-xx)<ans){
        ans = abs((element+arr[i])-xx);
         s = element;
         f = arr[i];
         sum = element+arr[i];
        }
    if(abs((element+arr[i])-xx)==ans){
        if(element+arr[i]<sum){
         s = element;
         f = arr[i];
         sum = element+arr[i];
        }
    }
    x+=arr[i];
    
    }
    cout<<f<<" "<<s;
}
int main(){
    int arr[4] = {1, 4, 5, 7};
    int brr[4] = {10, 20, 30, 40};
    int m = sizeof(arr)/sizeof(arr[0]);
    int n = sizeof(brr)/sizeof(brr[0]);
    int x = 32;
    solve(arr, brr, m, n, x);
}

Output

1 30

Approach 2

We can also use a two-pointer approach to solve this problem. Initialize one pointer to the start of the first array and the second pointer to the end of the second array.

Three cases can occur:

Vamware

Case1: If the absolute difference between X and sum of pairs is smaller than the maximum difference so far, update the answer.

Case2: If the sum of elements is smaller than the given sum, increment the pointer of the first array.

Vamware

Case 3: If the sum of elements is greater than the given sum, decrement the pointer to the second array.

Python Programming

import sys
def solve(ar1, ar2, m, n, x):

    dif=sys.maxsize

    l = 0
    r = n-1
    left=1
    right=1
    while(l < m and r >= 0):
        if abs(ar1[l] + ar2[r] - x) < dif:
            left = l
            right = r
            dif = abs(ar1[l] + ar2[r] - x)
    
        if ar1[l] + ar2[r] > x:
            r=r-1
        else:
            l=l+1
    print(ar1[left])
    print(ar2[right])
ar1 = [1, 4, 5, 7]
ar2 = [10, 20, 30, 40]
m = len(ar1)
n = len(ar2)
x = 32
solve(ar1, ar2, m, n, x)

Output

1 
30

C# Programming

using System;

class Solution {
    static void solve(int []ar1,
            int []ar2, int m, int n, int x)
    {
        
        int dif = int.MaxValue;

        
        int left = 0, right = 0;
        int l = 0, r = n-1;
        while (l < m && r >= 0)
        {
            if (Math.Abs(ar1[l] +
                    ar2[r] - x) < dif)
            {
                left = l;
                right = r;
                dif = Math.Abs(ar1[l]
                            + ar2[r] - x);
            }
    
        
            if (ar1[l] + ar2[r] > x)
                r--;
            else 
                l++;
        }

        Console.WriteLine(ar1[left]);
        Console.Write(ar2[right]);
    }

    public static void Main()
    {
        int []ar1 = {1, 4, 5, 7};
        int []ar2 = {10, 20, 30, 40};
        int m = ar1.Length;
        int n = ar2.Length;
        int x = 32;
       
        solve(ar1, ar2, m, n, x);
    }
}

Output

1 
30

People are also reading:

Author: Vinay

I am a Full Stack Developer with a Bachelor's Degree in Computer Science, who also loves to write technical articles that can help fellow developers.

Leave a Reply

Your email address will not be published.