I am working on the following problem. Assume you have a sorted array of numbers:
a[1] > a[2] > ... > a[n]
and a threshold T. You want to determine all pairs (i,j) such that
a[i] + a[j] > T
in the most effective way, when (1) no other condition is required or (2) the pairs must be listed from the largest to the smallest (i.e., first the pair with largest value of a[i]+a[j], then the second largest value of the sum, etc).
For (1) there is an easy way, at cost O(1) per pair, which follows the lexicographic order of the pairs. I.e., first we list all feasible pairs starting with i=1, then those starting with i=2, etc, as long as the cost of a[i] > T/ 2. For fixed i, we enumerate all j=i+1,i+2,.. as long as a[i]+a[j] > T. Notice that, within each block (fixed i), the values a[i]+a[j] are decreasing, but overall, the list of pairs produced might not be fully sorted (for example, it could be a[2] + a[3] > a[1] + a[4], but the pair (1,4) is enumerated before (2,3)). The code is something like
1. i:=1;
2. WHILE (i <= n-1) AND (a[i] + a[i+1] > T)
3. j := i+1
4. WHILE (j <= n) AND (a[i] + a[j] > T)
5. Print(Found pair (i,j));
6. j:=j+1;
7. ENDWHILE;
8. i:=i+1;
9. ENDWHILE
I am wondering if also point (2), i.e., from the largest to the smallest pair, can still be done at cost O(1) per pair. I only have a solution which can do this at cost O(log n) per pair. The way to do this uses a max-heap containing, at each step, n-1 pairs. There is a pair in the heap for each possible value of the first element i=1,..,n-1 (i.e., there is a pair (1,j_1), a pair (2,j_2), etc, up to (n-1,j_{n-1}), where the j_k might not be all different, but it is always j_k > k. Furthermore, if (i,j) is on the heap, then all pairs (i,h) with i<h<j have already been enumerated. At the generic step, the next pair to be enumerated is the heap root, let it be (i,j). Then if a[i]+a[j] <= T, the algorithm stops. Otherwise: (a) if j<n, the root element (i,j) is overwritten with (i,j+1), and its cost is updated with a[i]+a[j+1] while (b) if j=n the cost of the root element is updated to be -INFINITE. Then, in time O(log n) the heap property is restored by letting the root element slide down the heap to its correct position (i.e., when it becomes larger than both its sons).
I would be very grateful if someone has already encountered this problem and has a solution (or has figured out now a solution) to produce the sorted pairs in a faster way. I understand that an objection might be: if we could produce each pair in time O(1), then, with threshold T=0, we could sort O(N) pairs, with N=n^2, in time O(N) instead of O(N log N), which can't be done. Yes, but these are not any N numbers, but the N numbers resulting from adding up two in n elements, which may make the problem simpler. Thank you for the attention.