Minimum Absolute Sum Pair - C++ Solution

1. Introduction

This blog post delves into a common algorithmic problem in array processing: finding a pair of elements in a sorted array that yields the absolute minimum sum. The challenge lies in identifying the pair whose sum is closest to zero, showcasing the application of two-pointer techniques in C++.

Problem

Given a sorted integer array, the task is to find a pair of elements whose sum has the minimum absolute value. If multiple such pairs exist, any one of them can be returned. If the array doesn't contain enough elements to form a pair, return (-1, -1).

Examples:

- Input: [-6, -5, -3, 0, 2, 4, 9]

Output: (-5, 4)

- Input: [-6, -2, 0, 1, 5]

Output: (-6, 5) or (-2, 1) or (0, 1)

- Input: [1]

Output: (-1, -1)

2. Solution Steps

1. Initialize two pointers: one at the start and the other at the end of the array.

2. Keep track of the pair with the minimum absolute sum.

3. Iterate over the array with the two pointers:

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

- If the absolute sum is less than the current minimum, update the minimum and the pair.

- Move the pointers inward based on the sum's relation to zero.

4. Return the pair with the minimum absolute sum.

3. Code Program

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

// Function to find the pair with the minimum absolute sum
pair<int, int> findMinAbsSumPair(vector<int>& nums) {
    if (nums.size() < 2) return {-1, -1}; // Check for sufficient elements

    int left = 0, right = nums.size() - 1;
    int minSum = INT_MAX;
    pair<int, int> minPair = {-1, -1};

    while (left < right) {
        int sum = nums[left] + nums[right];
        int absSum = abs(sum);

        // Update the pair if a new minimum is found
        if (absSum < minSum) {
            minSum = absSum;
            minPair = {nums[left], nums[right]};
        }

        // Move pointers based on the sum
        if (sum < 0) {
            left++;
        } else {
            right--;
        }
    }

    return minPair;
}

int main() {
    vector<int> nums = {-6, -5, -3, 0, 2, 4, 9};
    auto result = findMinAbsSumPair(nums);
    cout << "Minimum Absolute Sum Pair: (" << result.first << ", " << result.second << ")" << endl;
    return 0;
}

Output:

Minimum Absolute Sum Pair: (-5, 4)

Explanation:

The findMinAbsSumPair function employs a two-pointer approach to scan the sorted array. Starting with pointers at the beginning and end of the array, it iterates to find the pair whose sum is closest to zero. This is done by calculating the sum of the pair and updating the minimum sum and corresponding pair as needed. The pointers are moved inward based on whether the current sum is less than or greater than zero. This approach ensures that the pair with the minimum absolute sum is efficiently found.