Finding the maximum number from two arrays preserving relative order

Problem

You are given two arrays of length M and N having elements in the range 0-9.
Your task is to create the maximum number of length K from elements of these two arrays such that the relative order of elements is the same in the final number as in the array, they are taken from

i.e. If two elements a, and b are taken from array1 and a comes before b in array1 so in the final number a should come before b (Relative order kept same).

 Example: N=4 and M =6
 Array1 = { 3 , 4, 6,5}
Array2 ={9,1,2,5,8,3}

Suppose K = 5, then the number will be {9,8,6,5,3}
You can see {9,8,3} are taken from Array2 in the same order as they are in Array2.
Similarly {6,5} are taken from Array1 in the same order and number 98653 is the maximum possible number.


[UPDATE 02-24-23]: Solved again. Got stuck with a possible exploration of using dynamic programming initially. The second solution was using the MaxHeap instead of the sorted list. It was awfully inefficient since I had to put each already seen item back into the heap, which takes $O(log (N+M)$.

A better way by far is to use a greedy algorithm with tracking of the positions from which elements from the list M, N were taken to ensure the relative order is preserved. Even then, it took 1 hr to fix the bug.

This is one of the Google interview questions. To be honest, it took me 3 days (although the actual time spent was around 7 hours), to find the solution.

I assigned "Difficult" to this problem even though some people find this problem easier than other one.

My initial algorithm was based on the DFS with backtracking, which takes $O(K (N+M)!)$.
My second attempt took longer than the initial attempt since I forgot how I solved it before and wanted to find after than polynomial time, which I failed.

Given, Array1 with the size of N and Array 2 with the size of M, the new algorithm took the idea of merging the two arrays and sorting the merged array. It iterated over the merged array K times to find the maximum value with the size of K.

Here is brought algorithm:

- In the list O, sort all numbers in descending order with their position and the name of the array to they belong.

for k = 0; k  <K; k++:

 iterate the numbers from O

  for number, C from O:

  - take the largest unused numbers

  - check if the position of the number is later than lastly taken number's position in the array M or N.

  - check if the remaining numbers in M, N are still larger or equal to the remaining numbers to choose (K - (k +1)) 

     - if so, add number C to the result set, R, and exit the for inner for loop.

 return the result set R.

The algorithm itself is quite simple but the process of coming up with the algorithm was quite painful.
Running time of this algorithm is $$O( K * (M+N))$$
Code from 02-24-23:

UPDATE(2019-07-20): solved the problem again but could not come up with a correct solution.

I was stuck with the idea of using dynamic programming not able able to figure up what to do with two arrays, M, N, and the position of lastly taken number from them.

I also found that the original code had some inefficient code around the while loop. Fix that problem in a python solution.

Rewrite the code with the algorithm above in python.



Practice statistics:

23:10: write up the code. (with a bug)
14:58: debug the code. (there was a bug in the code.)

Total: 38.09

The original solution from 2016



Practice statistics

3 days: to finally come up with the algorithm running in $O( K(M+N) )$