How to get the K smallest Products from pairs from two sorted Arrays?

Question

Two sorted arrays are given. We have to find the K smallest products from the pairs from these arrays. I could think of a mnlogk solution but this solution works even if the arrays are not in sorted order. Can we make use of this sorted order and find a better solution?

I tried using max heap of size k for obtaining the mnlogk solution.

Input: nums1 = [-2, -1, 0, 1, 2], nums2 = [-3, -1, 2, 4, 5], k = 3 Output: [-10, -8, -6] Explanation: -2 * 5, -2 * 4, 2 * -3

Answer 1

Instead of using the heap, try to generate products in the sorted order.

Imagine an n*m grid formed by indices into the respective arrays. At any given point of time the grid is partitioned into the "inspected" and "not yet inspected" parts. We shall keep an invariant, namely that a product of every inspected pair is less than the product of a not inspected. The hard part is to prove that the border separating them has O(n+m) pairs; the fact that the arrays are sorted is essential for the proof.

Now, you may test the products along the border, take the minimal, and modify the border accordingly. This operation will take O(n+m) time, and would be performed k times. An overall complexity is O(k(n+m)).

And the final optimization: the above plan recomputes many products along the border over and over again. Representing the border as a sorted map may drive the complexity down to O(k log(n+m)).