Question Name: Min-Abs-Sum-Of-Two or MinAbsSumOfTwo
There are two O(nlogn) solutions for this question. Both solutions have the same overall time complexity and space complexity. And both solutions need to sort the array in non-decreasing order first.
The first solution would sort the array with O(nlogn). Then for each element X in array, we could use binary search O(logn) to find the closest element Y to –X, so that |X+Y| is the closest to 0 (similar with the problem 3Sum-closest). To try all N elements, we need O(nlogn) to get N result as |X+Y|. Finally, linear time is needed to find the minimal one |X+Y|, which could be done while trying each round. Totally the time complexity is O(nlogn).
The second solution sorts the array with O(nlogn). We set two pointers (X and Y) to each end, and move the pointers from outside to inside by one or zero step in each round until them meet. The final result must be one of X and Y combination. Since each element in the sorted array will be accessed one and only one time, the time complexity is O(n). Totally the time complexity is O(nlogn). We will prove that, we definitely will meet the right X and Y combination in our method.
Without loss of generality, we consider X and Y are two different elements. ASSUME the array A is already SORTED, and the RIGHT ANSWER is in the position X and Y like:
We are accessing the elements once and only once. So there are two cases:
- We are firstly accessing the X and Y at the same time. Proved.
- We are firstly accessing the X and Y at different time. Without loss of generality, we access X firstly.
a. If A[X] + A[Y] >=0: the array is sorted , so for all i > Y, we have
A[X] + A[i] >= A[X] + A[i-1] >= 0.
=> A[X] + A[-1] >= A[X] + A[-2] >= … >= A[X] + A[Y+1] >= A[X] + A[Y] >=0
=> |A[X] + A[-1]| >= |A[X] + A[-2]| >= … >= |A[X] + A[Y+1]| >= |A[X] + A[Y]| >=0.
So our algorithm will guide us to move from any position after Y to Y finally.
b. If A[X] + A[Y] < 0: let a = |A[X] + A[Y]|, A[X] + A[Y+1] >= A[X] + A[Y] = -a with sorted array:
If A[X] + A[Y+1] == -a or a, switch to prove with answer positions (X, Y+1);
If A[X] + A[Y+1] is in range (-a, a), then |A[X] + A[Y+1]| < a = |A[X] + A[Y]|. It is contradict with the assumption |A[X] + A[Y]| is the minimal. Thus this case is not possible.
If A[X] + A[Y+1] > a > 0, prove with the steps in 2.a.
End of proof.
A.sort() # Sort A in non-decreasing order
if A >= 0: return A + A # All non-negative
if A[-1] <= 0: return -A[-1] - A[-1] # All non-positive
front, back = len(A)-1, 0
minAbs = A[-1] + A[-1] # Final result
# Travel the array from both ends to some center point.
# See following post for the proof of this method.
while back <= front:
temp = abs(A[back] + A[front])
# Update the result if needed
if temp < minAbs: minAbs = temp
# Adjust the pointer for next trying
if abs(A[back+1] + A[front]) <= temp: back += 1
elif abs(A[back] + A[front-1]) <= temp: front -= 1
else: back += 1; front -= 1