LeetCode Q321: Create Maximum Number (hard)

Given two arrays of length m and n with digits 0-9 representing two numbers. Create the maximum number of length k <= m + n from digits of the two. The relative order of the digits from the same array must be preserved. Return an array of the k digits. You should try to optimize your time and space complexity.

Example 1:

nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
return [9, 8, 6, 5, 3]

Example 2:

nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
return [6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3
return [9, 8, 9]

Solution:
First, this question remind me of my answer to LeetCode Q316 Remove Duplicate Letters, in which you should use greedy algorithm to choose optimal answer in current step. Actually, this question is similar to Q316 in the sense that we do need to be greedy when choosing each digit.

Since the order of numbers chosen from each array should keep their original order, this means, the number composed with these chosen digits has to be the largest one among all number chosen from the same array. So, if two numbers chosen from both arrays can be both the largest ones, the number merged from them must be the largest too!

This is the key of solving this problem.

This question takes me entire morning to solve, and have a lot of corner cases you should take care of.