Algorithm for finding minimum value of abs(A[i]+A[j]-k)

Question

I have an integer array A containing both positive and negative numbers. I have to find the minimum value of abs(A[i] + A[j] - k), where i != j.

I thought of sorting the array and using the two-pointer approach (as described at https://www.geeksforgeeks.org/two-pointers-technique/) and find the minimum. Time complexity is O(n*log(n)). Can this be done in O(n)?

Answer 1

Assuming that the O(n) requirement applies after any sorting (or that your problem domain supports linear-time sorting), you can use a trivial variation on the two-pointers algorithm (even for the case with two distinct arrays, where presumably one would not require i!=j). Consider the sums of the elements of two sorted arrays laid out in a rectangle:

    A= 4  9 17 22 29
 B= 7 11 16 24 29 36
   19 23 28 36 41 48
   20 24 29 37 42 49
   35 39 44 52 57 64

Suppose that k=40. By checking the lower-leftmost value (which is smaller), we can immediately rule out most of a column as containing the closest value, since those values must be even smaller:

    A= 4  9 17 22 29
 B= 7    16 24 29 36
   19    28 36 41 48
   20    29 37 42 49
   35 39 44 52 57 64

So we next check the value to the right (which is to say we increment the pointer into A). It is larger than k, so it eliminates the rest of that row:

    A= 4  9 17 22 29
 B= 7    16 24 29 36
   19    28 36 41 48
   20    29 37 42 49
   35 39 44

The next move must then be --b. Continuing this way cuts a path through the rectangle:

    A= 4  9 17 22 29
 B= 7          29 36
   19          41
   20    29 37 42
   35 39 44

You can move either direction (or diagonally) on an exact match (or just bail early if one hit is enough). In general, the path may exit the rectangle other than at a corner. For the case with only one array, you can stop as soon as it hits the diagonal (i.e., when i>=j), disregarding any last value stepped to.

This path obviously has O(n) entries, since at every step it moves up or right (or both). One of them must be the closest to k (here, 4+35 and 22+19 are tied).

See also X+Y sorting; this problem is a sort of "X+Y binary search".