title: efficient sorted Cartesian product of 2 sorted array of integers
body: <p>Need <strong>Hints</strong> to design an efficient algorithm that takes the following input and spits out the following output.</p>
  
  <p>Input: two sorted arrays of integers A and B, each of length n</p>
  
  <p>Output: One sorted array that consists of Cartesian product of arrays A and B.</p>
  
  <pre><code>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
  </code></pre>
  
  <p>Here are my attempts at solving this problem.</p>
  
  <p>1) Given that output is n^2, Efficient algorithm can't do any better than O(n^2) time complexity.</p>
  
  <p>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.</p>
  
  <p>Finally I have O(n^2logn) time and O(n^2) space complexity algorithm.</p>
  
  <p>There must be a better algorithm because I've not made use of <strong>sorted</strong> nature of input arrays. </p>