Find the closest pair from two arrays

JavaView on GFG

Intuition

Find pair (one from each sorted array) with sum closest to a target.

Algorithm

1Two pointers: i starts at end of arr1, j starts at beginning of arr2. Move based on sum vs target.

Common Pitfalls

•Similar to two-sum on two sorted arrays. O(m+n) after sorting. Track minimum |sum-target|.

Find the closest pair from two arrays.java

Java

// Approach: Sort both arrays. Two pointers: advance the pointer with smaller value, track minimum absolute diff.
// Time: O(n log n + m log m) Space: O(1)
import java.util.*;

class Solution {
    public static ArrayList<Integer> findClosestPair(int arr1[], int arr2[], int x) {
        int n = arr1.length, m = arr2.length;
        int i = 0, j = m - 1;
        int diff = Integer.MAX_VALUE;
        ArrayList<Integer> result = new ArrayList<>(2);

        while (i < n && j >= 0) {
            int sum = arr1[i] + arr2[j];
            int currDiff = Math.abs(sum - x);

            if (currDiff < diff) {
                diff = currDiff;
                result.add(0, arr1[i]);
                result.add(1, arr2[j]);
            }

            // Move pointers
            if (sum > x)
                j--;
            else 
                i++;
        }

        return result;
    }
}

Was this solution helpful?