How to find the number of perfect pairs in an array

Question

The original question link is here: https://leetcode.com/discuss/interview-question/1781247/tusimple-oa-perfect-pairs

A pair of integers (x,y) is perfect if both the below conditions are met:

min(|x-y|,|x+y|)<=min(|x|,|y|)
max(|x-y|,|x+y|)>=max(|x|,|y|)

Given an array of length n, find the number of perfect pairs (arr[i],arr[j]) where 0<=i<j<n

Here min(a,b) is the min of a and b, max(a,b) is the max of a and b, and |x| is the absolute value of x.

Exmaple:

arr = [-9,6,-2,1] -> ans=2
arr = [2,5,-3] -> ans = 2

How can I solve this with time complexity less than O(n^2)?

Answer 1

As others have mentioned, the second condition is always met.

We only have to care about the first condition, which you may notice that all the possibilities x and y are negative, x and y are non-negative, x is negative and y is non-negative, x is non-negative and y is negative, would end up the same. Thus, we can assume all the numbers are non-negative.

Then, the first condition became y-x <= x, or equivalently y <= 2x if x is smaller. We can just assume that x is smaller, because: if (x,y) satisfies the conditions, then (y,x) would also be; yet, only one pair between those two satisfies the condition 0 <= i < j < n (where i, j are indices of the numbers x, y)

To utilize the assumption, let's change sign of all negative numbers in the input array, then sort the array.

Then, we iterate the array to count the number of pairs. For each y, we can quickly binary search for the closest value of y/2. All the numbers from that value to the number right before y would satisfy the conditions. The count for each y like that is just the differences in indices between y and the first potential x.

Aggregating those counts of each individual y gets us the final result.

The time complexity of the above idea is O(nlogn), where we iterate through the array a few times independently, and for the iteration to check for each y, we apply the binary search which is O(logn).