efficient sorted Cartesian product of 2 sorted array of integers

Question

Need Hints to design an efficient algorithm that takes the following input and spits out the following output.

Input: two sorted arrays of integers A and B, each of length n

Output: One sorted array that consists of Cartesian product of arrays A and B.

For Example: 

Input:
A is 1, 3, 5
B is 4, 8, 10
here n is 3.

Output:
4, 8, 10, 12, 20, 24, 30, 40, 50

Here are my attempts at solving this problem.

1) Given that output is n^2, Efficient algorithm can't do any better than O(n^2) time complexity.

2) First I tried a simple but inefficient approach. Generate Cartesian product of A and B. It can be done in O(n^2) time complexity. we need to store, so we can do sorting on it. Therefore O(n^2) space complexity too. Now we sort n^2 elements which can't be done better than O(n^2logn) without making any assumptions on the input.

Finally I have O(n^2logn) time and O(n^2) space complexity algorithm.

There must be a better algorithm because I've not made use of sorted nature of input arrays.

Answer 1

If there's a solution that's better than O(n² log n) it needs to do more than just exploit the fact that A and B are already sorted. See my answer to this question.

---

Srikanth wonders how this can be done in O(n) space (not counting the space for the output). This can be done by generating the lists lazily.

Suppose we have A = 6,7,8 and B = 3,4,5. First, multiply every element in A by the first element in B, and store these in a list:

6×3 = 18, 7×3 = 21, 8×3 = 24

Find the smallest element of this list (6×3), output it, replace it with that element in A times the next element in B:

7×3 = 21, 6×4 = 24, 8×3 = 24

Find the new smallest element of this list (7×3), output it, and replace:

6×4 = 24, 8×3 = 24, 7×4 = 28

And so on. We only need O(n) space for this intermediate list, and finding the smallest element at each stage takes O(log n) time if we keep the list in a heap.