Evaluate all pair combinations in an array for a condition in n log n time complexity

Question

Task - Consider an array of n elements. Count the number of pairs that satisfy condition X (sum of the two elements < an arbitrary number, k) .

The basic approach I could think of would be O(n^2), where I evaluate all n*(n-1)/2 pairs. How can I solve the problem in a better time frame i.e., O(n log n) or less?

The best approach so far was to sort the array, find where a+b smaller than k then add indice of a to solution. But the process still has to go through n-1 'b's to check for each of them. It's better but still doesn't improve the worst case.

Also, this isn't homework. I came across this while preparing for a competition.

Answer 1

if you need ALL results on an arbitrary condition (say C(a,b) = (sha1(a~c)^sha1(c~a))%2 == 0 with ~ as concatenation) then there are n*(n-1)/2 values you need to output that are all independent; so no there is no better way,

but if the result of one pair tells you something about the result of another pair then that information can be used to speed things up. like in your example if sum > k then you sort and for each number you check each in order (forwards or backwards). On the first true result you add the numbers still remaining. This will be O(n log n + r) with r number of true results.

edit: on second thought you can use a binary search each on each number a find the first number that is larger than k-a reducing it to a O(n log n) completely

Answer 2

Given an array A of length n and a bound k find all indices (i,j) such that A[i] + A[j] < k.

This can actually be solved in O(n log n).

The set I of indices (i,j) you are looking for has some structure when the array is sorted in increasing order. Indeed if (i₀,j₀) belongs to I then, whenever i ≤ i₀ and j ≤ j₀ the indice pair (i,j) also belongs to I. This means that I looks like this:

...........
++*........
+++........
+++........
+++........
+++........
+++++*.....
++++++.....
++++++++*..
+++++++++..

where a dot . denotes a pair that does not belong to I while a plus + or a star * denotes a pair belonging to I. As you see, the presence of an indice denoted + is implied by the presence of some indice denoted by a star * so only the latter need to be searched.

1. Sort the array in O(n log n)

2. Set i to the largest indice so that A[i] ≤ k in O(n) and set j to 1 if you use Pascal or 0 if you use another language, this latter operation is O(1).

3. If A[i] + A[j] is greater than k then decrease i and try 3. again, otherwise go to 4.

4. If A[i] + A[j+1] is smaller than k then increase j and try 4. again.

5. We have found a point marked with a * add it to I and decrease i.

6. If A[i] + A[j+1] is greater than k then decrease i and try 6. again.

7. Go to 4.

Do not forget to fix the algorithm and add boundary checking and adequate exit conditions. In the repetitive part 3.-7. the algorithm only visits indices that are on the frontier between I and its complement. This frontier has length at most 2n so the overall cost of this exploration is O(n). The repetitive part 3.-7. is just a contrived way to say: visit that frontier, remembering whenever you have to change direction.

The total cost of the algorithm is then O(n log n) + O(n) + O(1) + O(n) = O(n log n).

P.S.: Actually the picture should be symmetric around the first diagonal and the algorithm can stop exploring the frontier when it meets the diagonal. These are small details.

P.P.S.: Of course, if your condition does not have structure, you must explore all combinations.

Answer 3

In that general way you explain it: no, can't be done.

As soon as you need to evaluate all pair combinations you pretty much have a O(n²) runtime.

If there is some way to exclude some combinations (for example for a given item, you know that no combination will fulfill the condition), then you can get better runtime behaviour.

For example, if you know the smallest number in your array to be min, then skipping all element e where e + min > k can help you get a better effective runtime (but it won't reduce the worst case).

Another approach that's useful if you don't need the best solution, but "good enough" is enough, is to use a heuristic. For example, if you can "guess" that a given item is unlikely to be in the ideal combination, you can skip it. This again will improve performance but can lead to you missing the ideal combination.