Create a maximum number of length K from two arrays of length M and N.


  • 0
    S

    I came across this question and found it very interesting. Here is the question in its entirety:

    We have two arrays of length M and N each having numbers as elements in the range 0-9. We want to create a maximum number of length K from the elements of these two arrays such that 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,b are taken from array1 and and a comes before b in array1 then, 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]

    If K = 5, then the maximum number that can be created is [9,8,6,5,3].
    [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 maximum possible number.


  • 0

    Hi @Spunkerspawn, are duplicate digits allowed in each input array?

    For example: Array1 = [1, 1, 2, 2], Array2 = [1, 2, 3, 5, 5], if K = 5, the max number is [5, 5, 1, 2, 2].


  • 0
    S

    Let's assume that duplicates are not allowed.


  • 0

    I see, one solution in my mind is bfs/dfs, but I guess you might have a better solution, e.g. some math magic :)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.