27. Find the closest pair from two arrays

The problem can be found at the following link:

My Approach

I have implemented a solution to find the closest pair from two arrays using a two-pointer approach. Here are the steps I followed:

Initialize two pointers, a and b, to the start of the first and second arrays, respectively.
Initialize a variable nin to store the minimum absolute difference found so far and set it to INT_MAX.
Initialize an empty vector out to store the closest pair.
Iterate through both arrays while a is less than n and b is greater than or equal to 0.
- Calculate the sum of the elements at the current positions of the pointers: sum = arr[a] + brr[b].
- Check if the absolute difference between sum and the target value x is less than the current minimum difference nin. If so, update nin and set out to the current pair [arr[a], brr[b]].
- If sum is greater than x, decrement b to try a smaller element from the second array. Otherwise, increment a to try a larger element from the first array.
- Repeat this process until both pointers have been exhausted.

Time and Auxiliary Space Complexity

Time Complexity: The time complexity of this solution is O(n + m) because we iterate through both arrays once, where n is the size of the first array and m is the size of the second array.
Auxiliary Space Complexity: The auxiliary space complexity is O(1) as we use a constant amount of extra space for variables.

Code (C++)

class Solution {
public:
    vector<int> printClosest(int arr[], int brr[], int n, int m, int x) {
        vector<int> out;
        int nin = INT_MAX;
        
        int a = 0, b = m - 1;
        while (a < n && b >= 0) {
            int sum = arr[a] + brr[b];
            if (abs(sum - x) < nin) {
                out = {arr[a], brr[b]};
                nin = abs(sum - x);
            }
            if (sum > x)
                --b;
            else
                ++a;
        }
        return out;
    }
};

Contribution and Support

Previous09-2023(sep)Next09-2023(sep)

Last updated 1 year ago

Was this helpful?

My Approach

I have implemented a solution to find the closest pair from two arrays using a two-pointer approach. Here are the steps I followed:

Initialize two pointers, a and b, to the start of the first and second arrays, respectively.

Initialize a variable nin to store the minimum absolute difference found so far and set it to INT_MAX.

Initialize an empty vector out to store the closest pair.

Iterate through both arrays while a is less than n and b is greater than or equal to 0.

Calculate the sum of the elements at the current positions of the pointers: sum = arr[a] + brr[b].
Check if the absolute difference between sum and the target value x is less than the current minimum difference nin. If so, update nin and set out to the current pair [arr[a], brr[b]].
If sum is greater than x, decrement b to try a smaller element from the second array. Otherwise, increment a to try a larger element from the first array.
Repeat this process until both pointers have been exhausted.

Time and Auxiliary Space Complexity

Time Complexity: The time complexity of this solution is O(n + m) because we iterate through both arrays once, where n is the size of the first array and m is the size of the second array.

Auxiliary Space Complexity: The auxiliary space complexity is O(1) as we use a constant amount of extra space for variables.

Code (C++)

class Solution {
public:
    vector<int> printClosest(int arr[], int brr[], int n, int m, int x) {
        vector<int> out;
        int nin = INT_MAX;
        
        int a = 0, b = m - 1;
        while (a < n && b >= 0) {
            int sum = arr[a] + brr[b];
            if (abs(sum - x) < nin) {
                out = {arr[a], brr[b]};
                nin = abs(sum - x);
            }
            if (sum > x)
                --b;
            else
                ++a;
        }
        return out;
    }
};