3
$\begingroup$

Input: An array $a$ of integers $[a_{1}, \cdots, a_{n}]$, and a positive integer $k$.

Output: The the top-k products of pairs in $a$.

Example: $a = [7,6,5,4,3,2,1],k=3$ , output $(42,35,30)$, with corresponding pairs $(7,6),(7,5),(6,5)$.

A naive solution would can be done in $O(k^{2}\log{k} + n\log{n})$, which sort the array first and enumerate over the cartesian product of the first $k$ elements.

I can afford the cost of sorting the array but when $k$ is large, $k^{2}\log{k}$ is costly, is there any better solution?

$\endgroup$
  • 1
    $\begingroup$ This is a classical question which can be solved in $O(n\log n + k\log k)$. See for example this question on stackoverflow. $\endgroup$ – Yuval Filmus May 31 '18 at 13:55
  • $\begingroup$ Thanks, but the the link is about top k sum, not top k product. $\endgroup$ – Keith May 31 '18 at 16:32
  • 1
    $\begingroup$ @Keith What is the difference? $\endgroup$ – gnasher729 May 31 '18 at 16:49
  • $\begingroup$ It's basically the same problem. Assuming for simplicity that all elements are positive, you can convert product to sum by taking log (though in this particular case, you can just run the same algorithms). $\endgroup$ – Yuval Filmus May 31 '18 at 16:50
  • $\begingroup$ If elements are allowed to be zero or negative, you need to work a bit harder, using the original algorithm as a black box. Details left to you. $\endgroup$ – Yuval Filmus May 31 '18 at 16:52

Your Answer

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

Browse other questions tagged or ask your own question.