Closest pair sum to x in two sorted arrays

user_16689093 0
Viewed 275

I came across a coding problem that goes as follows:

Given 2 sorted arrays: A and B, and a positive integer x, print the closest pair (one from each array) sum to x.

Example:

B = {10,20,30,40} , A = {0,4,6,11,11} , x = 13.

Output: 4 and 10.

This is what I've tried:

    int i = 0;
    int j = b.length - 1;
    int closest = Integer.MAX_VALUE;
    String s = "";
    while (i <= a.length - 1 && j >= 0)
    {
        if (Math.abs((b[j] + a[i]) - x) < closest || Math.abs((b[j] + a[i]) - x) == 0)
        {
            closest = Math.abs(x - (b[j] + a[i]));
            s = a[i] + " " + "and" + " " + b[j];
            if (j != 0)
                j--;
        }
        if (Math.abs((b[j] + a[i]) - x) > closest || j == 0)
            i++;
    }
    System.out.println(s);

This code works fine with most inputs I tested including the example mentioned above, except when the input x is 70 then the output is 11 and 30, instead of 11 and 40.

What I'm trying to understand basically is when should I decrease j and when should I increment i so that the code works on every possible x input.

The solution must be O(n) time complexity.

Appreciate the help! (If you find mistakes in my English, please let me know, I'm trying to improve.)

algorithm java
3 Answers

You should use Two Pointer method to get desired result. Below code will work for you.

       while (i <= a.length-1 && j >= 0) {
    
            if (Math.abs((b[j]+a[i]) - x ) < closest || Math.abs( (b[j]+a[i]) - x) == 0) {
                closest = Math.abs(x - (b[j]+a[i])) ;
                s = a[i] + " " +  "and" + " " + b[j];
            }
            
            if (b[j]+a[i] > x) j --;
            else i++;
        }

Time complexity is definitely O(n).

For detailed instructions please visit here on GeeksforGeeks.

user_166592140 
public static int[] getClosestPairSum(int[] A, int[] B, int x) {
    TreeSet<Integer> unique = new TreeSet<>();

    for (int a : A)
        unique.add(a);

    int absDiff = -1;
    int[] res = { 0, 0 };

    for (int b : B) {
        for (Integer aa : Arrays.asList(unique.floor(x - b), unique.ceiling(x - b))) {
            if (aa == null)
                continue;

            int curAbsDiff = Math.abs(x - b - aa);

            if (absDiff == -1 || curAbsDiff < absDiff) {
                absDiff = curAbsDiff;
                res[0] = aa;
                res[1] = b;
            }
        }
    }

    return res;
}
user_34613970

Basically similar to question's code (a bit simpler?):

// returning an array so I can check against brute force algorithm
private static int[] closestPair(int[] a, int[] b, int x) {
    int closest = Integer.MAX_VALUE;
    int[] result = { -1, -1 };    // could use null
    int i = 0;
    int j = b.length-1;
    while (i < a.length && j >= 0) {
        int diff= (a[i] + b[j]) - x;

        // is it closer?
        if (abs(diff) < closest) {
            closest = abs(diff);
            result[0] = a[i];
            result[1] = b[j];
        }

        // which pointer to change for next iteration
        if (diff == 0) break;  // shortcut, can't get closer
        if (diff < 0) {
            i++;               // sum was less than x, try higher value
        } else {
            j--;               // sum was greater, try a smaller one
        }
    }
    return result;
}
user_163206750
Related