3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ The two-pointer algorithm should work if you are careful enough. Try a few more times. $\endgroup$ – Yuval Filmus Jul 19 '17 at 12:15
  • $\begingroup$ Perhaps you should keep two extra variables that indicate how many copies of the current two values there are. $\endgroup$ – Albert Hendriks Jul 19 '17 at 12:32
  • 1
    $\begingroup$ Is it sorted. You refer to n and m but you don't refer to two arrays. $\endgroup$ – paparazzo Jul 19 '17 at 12:47
6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.