Number of Pairs in Array

so hey, I've been recently reading about the Two-Pointer algorithm that allows us to find pairs $(i,j)$ such that $a[i] + a[j] = x$ in $O(m+n)$ instead of the trivial $O(mn)$ time.

I was wondering how can I find the number of pairs $(i,j)$ in time less than $O(mn)$. I was trying to use Two-Pointer but it seems that it doesn't work when there duplicate elements because there can be no way of moving one pointer without missing some pairs like $[1, 1, 2, 3, 3]$ and $x = 4$ or maintaining the linear time, unless I'm missing something here.


Is there is some magical way of finding the number of pairs $(i,j)$ such that $a[i] + a[j] = x$ in less than $O(mn)$ time?

You observed correctly that the number of pairs can grow quadratically with input size. In the worst case, the array contains only two types of numbers, but with great multiplicity.

$$[1,1,1,1,1,2,2,2,2,2]$$

Here, each of the five ones can be combined with each of the five twos, thus creating 25 pairs that sum up to three. It is generally impossible to visit each pair once and maintain linear time complexity.

Luckily, it is not neccessary to visit each pair once, as we can calculate the multiplicity of the pair from the multiplicities of its members. In this case:

$$5 \cdot 5 = 25$$

To find all pairs in linear time, run-length encode the array first. So

$$[0,1,1,1,1,1,2,2,2,2,2,3]$$

becomes

$$[(0,1),(1,5),(2,5),(3,1)]$$

Then, apply the two-pointer algorithm and calculate the multiplicity of each resulting pair directly. Here, the result could be a pair of zero and three with multiplicity one, and a pair of one and two with multiplicity 25.

$$[(0,3,1),(1,2,25)]$$

In total, there are 26 pairs.

StackExchange Computer Science Q#78090, answer score: 6