How to find all ordered pairs of elements in array of integers whose sum lies in a given range of value

Question

Given an array of integers find the number of all ordered pairs of elements in the array whose sum lies in a given range [a,b]

Here is an O(n^2) solution for the same

'''
counts all pairs in array such that the 
sum of pair lies in the range a and b
'''
def countpairs(array, a, b):
    num_of_pairs = 0
    for i in range(len(array)):
        for j in range(i+1,len(array)):
            total = array[i] + array[j]
            if total >= a and total <= b:
                num_of_pairs += 1
    return num_of_pairs

I know my solution is not optimal What is a better algorithm for doing this.

Answer 1

1. Sort the array (say in increasing order).
2. For each element x in the array:
   • Consider the array slice after the element.
   • Do a binary search on this array slice for [a - x], call it y0. If no exact match is found, consider the closest match bigger than [a - x] as y0.
   • Output all elements (x, y) from y0 forwards as long as x + y <= b

The time complexity is of course output-sensitive, but this is still superior to the existing algo:

O(nlogn) + O(k)

where k is the number of pairs that satisfy the condition.

Note: If you only need to count the number of pairs, you can do it in O(nlogn). Modify the above algorithm so [b - x] (or the next smaller element) is also searched for. This way, you can count the number of 'matches' each element has in O(logn) simply from the indices of the first and last match. Then it's just a question of summing those up to get the final count. This way, the initial O(nlogn) sorting step is dominant.