Closest Pair - C++ Solution

1. Introduction

In this blog post, we'll address a common problem in array processing: finding a pair of elements from two sorted arrays such that their sum is closest to a given target value. This problem is a prime example of the two-pointer technique and is widely applicable in algorithm design and data analysis.

Problem

Given two sorted arrays X[] and Y[], and an integer k, the objective is to find a pair (x, y) - where x is from X[] and y is from Y[] - such that the sum of x and y is closest to k. If multiple pairs qualify, any one can be returned. If no such pair exists, the function should return (-1, -1).

Example:

Input: X[] = [1, 8, 10, 12], Y[] = [2, 4, 9, 15], k = 11

Output: (1, 9)

2. Solution Steps

1. Initialize two pointers: one at the start of X[] and the other at the end of Y[].

2. Keep track of the closest sum and the corresponding pair.

3. Iterate while both pointers are within their respective arrays.

4. Calculate the sum of elements pointed by the two pointers.

5. If this sum is closer to k than the previous closest, update the closest sum and the pair.

6. Move the first pointer forward if the sum is less than k, or move the second pointer backward if the sum is greater.

7. Continue this process until all pairs are checked.

8. Return the closest pair found, or (-1, -1) if no suitable pair is found.

3. Code Program

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// Function to find the closest pair from two arrays
pair<int, int> findClosestPair(vector<int>& X, vector<int>& Y, int k) {
    int xSize = X.size(); // Size of the first array
    int ySize = Y.size(); // Size of the second array
    int i = 0, j = ySize - 1; // Initialize two pointers
    int closestSum = INT_MAX; // To store the closest sum
    int x = -1, y = -1; // To store the closest pair

    // Loop until both pointers are within their respective arrays
    while (i < xSize && j >= 0) {
        int sum = X[i] + Y[j]; // Calculate the sum of the current pair
        // If this pair is closer to k than the previous closest, update closestSum and the pair
        if (abs(k - sum) < abs(k - closestSum)) {
            closestSum = sum;
            x = X[i];
            y = Y[j];
        }
        // Move pointers to find a closer sum
        if (sum < k) {
            i++; // Move the first pointer forward if sum is less than k
        } else {
            j--; // Move the second pointer backward if sum is greater than k
        }
    }
    return {x, y}; // Return the closest pair
}

int main() {
    vector<int> X = {1, 8, 10, 12};
    vector<int> Y = {2, 4, 9, 15};
    int k = 11;
    // Find and print the closest pair
    auto result = findClosestPair(X, Y, k);
    cout << "Closest pair: (" << result.first << ", " << result.second << ")" << endl;
    return 0;
}

Output:

Closest pair: (1, 9)

Explanation:

The findClosestPair function takes two sorted arrays X and Y, along with the target sum k. It utilizes two pointers, one at the start of X and the other at the end of Y, to find the closest sum to k. The function updates the closest pair whenever a closer sum is found and returns this pair. If no suitable pair is found, it returns (-1, -1).