How can I generate all possible sorted arrays from alternate elements of two sorted arrays?

Question

I recently encountered this question in an interview. I wasn't really able to come up with an answer to this. I started with, take first element from first array, and then find how many elements are greater than this element in the other array. But then, I mean, I don't know, couldn't really form a solution. The problem is as follows:

Given two sorted arrays A and B, generate all possible arrays such that first element is taken from A then from B then from A and so on in increasing order till the arrays exhausted. The generated arrays should end with an element from B.

Eg:
A = {10, 15, 25}
B = {1, 5, 20, 30}

The resulting arrays are:
  10 20
  10 20 25 30
  10 30
  15 20
  15 20 25 30
  15 30
  25 30

I am not looking for a code, just an algo/pseduo-code would do fine. Thanks!

Answer 1

How about using a directed graph with a BFS search of paths.

1. Create a directed graph where a directed edge is created from an element in array A to every element in array B if that element in B is greater. And vice verse. A directed edge is created from an element in array B to every element in array A if that element in A is greater.
2. Pick an element from A
3. Then use a BFS search to generate all possible paths.
4. Every time a path includes an element from B add that sub-path to your solution list of paths
5. Stop when all elements of A have been used as a search key

Update

Per suggestion by @MiljenMikic, you can exploit the fact that the arrays are sorted by speeding up Step 1. You don't have to search all elements in the other array to find greater-than elements. Just keep track of the last found and move the pointer forward as you search.

Answer 2

BFS solution that @dpmcmlxxvi proposed is interesting. In addition, I would suggest a recursive variant. Some basic points:

• one of the input arguments of your recursive function should be a boolean variable that will indicate whether you should add an element from A or from B; you will alternate this value in subsequent recursive calls

• arrays are sorted - use that information! When you see sorted arrays, always think of binary search - in this case you should recursively pass last added element and then, in the other array, binary search for the first element that is greater than that last element

• if the last added element was from B, add the current working array to the resulting list