Find the closest pair from two arrays

Posted in

Find the closest pair from two arrays
vinaykhatri

Vinay Khatri
Last updated on October 15, 2024

    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 the upper bound or a number at an index one less than the 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:

    Case1: If the absolute difference between X and the 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.

    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:

    Leave a Comment on this Post

    0 Comments