1
$\begingroup$

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?

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

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}$

$\endgroup$
  • $\begingroup$ 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..... $\endgroup$ – Macchiatow Feb 15 '16 at 13:57
  • $\begingroup$ counting a[y]+a[z]>9 on boundary looks linear now. overall looks like n2. thanks. $\endgroup$ – Macchiatow Feb 15 '16 at 15:31
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – Macchiatow Feb 15 '16 at 9:53
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 15 '16 at 10:09

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.