# Counting all $x,y,z$ such that $a[x] > a[y] + a[z]$

Given an array $a$, I want to count all triplets of indices $x,y,z$ such that $a[x] > a[y] + a[z]$.

I can think of two solutions:

1. Go over all triplets of indices $x,y,z$ directly. This takes time $O(n^3)$ and constant space.

2. Compute a new array consisting of all sums $a[y]+a[z]$, sort it, and then go over all $x$ and use binary search. This takes time $O(n^2\log n)$ and space $O(n^2)$.

Is it possible to improve on these solutions?

• What is "TreeSet"? What is "adding tails"? – David Richerby Feb 15 '16 at 9:39
• Please check that I retained your original intentions. – Yuval Filmus Feb 15 '16 at 9:40
• @YuvalFilmus seems just right! thanks. – Macchiatow Feb 15 '16 at 9:50

Let me try to sketch a method that counts the triplets by directly counting. Let me first assume that $a$ is sorted. I will also keep $x$ constant for this exposition (and iterate over $x$). For simplicity take $a[x]=0$, so the task is to count $(y,z)$ such that $a[y]+a[z]<0$. We can count the pairs, but not by going over all $n^2$ of them, but by following the "boundary" between negative and positive pairs. This is like counting the number of negative elements in a two dimensional array that is increasing in both dimensions. This seems to be possible in linear time? (for fixed $x$)

As an example we consider the following virtual two-dimensional array; i.e., it is not explicitly constructed, element $(y,z)$ just is $a[y]+a[z]$. We can count the elements $a[y]+a[z]>9$ by "walking" along the "boundary".

$\begin{array}{c|ccccc} a & 1 & 3 & 4 & 7 & 8 \\\hline 1 & 2 & 4 & 5 & 8 & 9 \\ 3 & 4 & 6 & 7 & \color{green}{10}& \color{green}{11}\\ 4 & 5 & 7 & 8 & \color{green}{11}& \color{green}{12}\\ 7 & 8 & \color{green}{10}& \color{green}{11}& \color{green}{14}& \color{green}{15}\\ 8 & 9 & \color{green}{11}& \color{green}{12}& \color{green}{15}& \color{green}{16} \end{array}$

• a is sorted array of positive ints. a[y]+a[z] > 0 always. If you have to calculate pairs there is no way to make it less than n2. Sorry I don't follow..... – Macchiatow Feb 15 '16 at 13:57
• counting a[y]+a[z]>9 on boundary looks linear now. overall looks like n2. thanks. – Macchiatow Feb 15 '16 at 15:31

Assuming the 3SUM conjecture, this cannot be solved in $O(n^{2-\epsilon})$ for any $\epsilon > 0$. For more lower bounds, I suggest you consult the 3SUM literature, which has recently been enjoying a renaissance; your problem seems even harder.

• I would be fine with O(n2log⁡n) and space O(n) . Run out of memory. Would it may be possible so a[y]+a[z] are streamed sorted (without of allocation n2 space and sorting later on)? – Macchiatow Feb 15 '16 at 9:53
• Such algorithms do exist for 3SUM, see for example the classic 4SUM algorithm of Schroeppel and Shamir. I don't know whether these techniques can be extended to your problem. – Yuval Filmus Feb 15 '16 at 10:09