Approach #1: Brute Force [Time Limit Exceeded]
Intuition
Our next digit in the answer either comes from nums1 or nums2.
Algorithm
Let's use recursive calls to maxNumber
to compute the answer. If nums1 is nonempty, we could either use it's first value in our answer or not, and similarly for nums2. The maximum of all these candidates is our answer.
Python
class Solution(object):
def maxNumber(self, nums1, nums2, k):
if k == 0:
return []
cand0 = cand1 = cand2 = cand3 = []
if nums1:
cand0 = self.maxNumber(nums1[1:], nums2, k)
cand1 = [nums1[0]] + self.maxNumber(nums1[1:], nums2, k1)
if nums2:
cand2 = self.maxNumber(nums1, nums2[1:], k)
cand3 = [nums2[0]] + self.maxNumber(nums1, nums2[1:], k1)
return max((cand0, cand1, cand2, cand3), key = lambda x: (len(x), x))
Complexity Analysis

Time Complexity: Let $$M, N$$ be the length of the given arrays, and $$K$$ the length of the desired final answer. An easy to find complexitybound is $$O(4^{M+N} * K)$$, as we do $$O(K)$$ work to create the new lists, and each function call may make up to 4 other function calls until both lists are empty.

Space Complexity: There are $$O(4^{M+N})$$ function calls with $$O(K)$$ length arrays, so the space complexity is also $$O(4^{M+N} * K)$$.
With more complicated analysis outside the scope of this article, tighter bounds are possible.
Approach #2: Naive Dynamic Programming [Time Limit Exceeded]
Intuition
We could cache intermediate results of our brute force, to avoid repeated function calls of the same arguments.
Algorithm
Let dp(i, j, k)
be the answer to the problem for input arguments nums1[i:], nums2[j:], k
. We will only compute the answer for these arguments if we haven't yet before.
class Solution(object):
def maxNumber(self, nums1, nums2, K):
memo = {}
def dp(i = 0, j = 0, k = K):
if (i, j, k) not in memo:
if k == 0:
ans = []
else:
cand0 = cand1 = cand2 = cand3 = []
if i < len(nums1):
cand0 = dp(i+1, j, k)
cand1 = [nums1[i]] + dp(i+1, j, k1)
if j < len(nums2):
cand2 = dp(i, j+1, k)
cand3 = [nums2[j]] + dp(i, j+1, k1)
ans = max((cand0, cand1, cand2, cand3),
key = lambda x: (len(x), x))
memo[i, j, k] = ans
return memo[i, j, k]
return dp()
Complexity Analysis

Time Complexity: Let $$M, N$$ be the length of the given arrays, and $$K$$ the length of the desired final answer. Every function call
maxNumber(nums1[i:], nums2[j:], k)
is explored, where $$0 \leq i < M$$, $$0 \leq j < N$$, $$0 \leq k \leq K$$, so there are $$O(MNK)$$ calls. In each call, we may do up to $$O(K)$$ work to create the new lists of length $$K$$. In total, this is a complexity of $$O(MNK^2)$$. 
Space Complexity: There are $$O(MNK)$$ function calls with $$O(K)$$ length arrays, so the space complexity is also $$O(MNK^2)$$.
Approach #3: Merge Subsets [Accepted]
Intuition
Consider the problem of k = len(nums1) + len(nums2)
. This is much easier to solve, because we do not need to consider the case of including neither value. When we are at the state represented by nums1[i:], nums2[j:]
, we should choose the next value in our answer based on whether nums1[i:]
or nums2[j:]
is larger.
Now, say we chose c
elements from nums1
, and kc
elements from nums2
. We can first preselect that number of elements from these arrays in a way that maximizes their lexicographic value. Then, we will solve the simpler problem explained above, for each possible value of c
.
Algorithm
The main difficulty is choosing c
elements from nums1
in lexicographically largest order. We maintain an answer stack: then, while the next digit is larger than the current last digit (and we can safely delete the digit), we should delete this current last digit.
Another difficulty is merging two subsets together by comparing their suffixes. We need to compare arr1[i:]
and arr2[j:]
: whichever is larger is the one we should choose the next element from. We use deques so that our shifting operation is cheaper in typical cases, and we still have a convenient A >= B
comparison. (Alternatively, we could use iterative slicing, by making a custom comparator that will walk through each array and compare the elements in turn.)
Python
class Solution(object):
def maxNumber(self, nums1, nums2, k):
def best(arr, k):
ans = collections.deque()
cuts = len(arr)  k
for x in arr:
while cuts > 0 and ans and ans[1] < x:
ans.pop()
cuts = 1
ans.append(x)
while cuts > 0:
ans.pop()
cuts = 1
return ans
def merge(dq1, dq2):
ans = []
while dq1 or dq2:
if dq1 >= dq2:
ans.append(dq1.popleft())
else:
ans.append(dq2.popleft())
return ans
ans = []
for c in range(k+1):
if c <= len(nums1) and kc <= len(nums2):
cand = merge(best(nums1, c), best(nums2, kc))
if cand > ans:
ans = cand
return ans
Complexity Analysis

Time Complexity: Let $$M, N$$ be the length of the given arrays, and $$K$$ the length of the desired final answer. We make $$O(K)$$ calls to functions
best
andmerge
. For eachc
, our calls tobest
are order $$O(M) + O(N) = O(M+N)$$, and our call tomerge
is $$O(K^2)$$ in the worst case, as in our comparison step we may need to make elementwise comparisons $$O(\sum_{i = 0}^{K} i)$$ many times. In total, this is $$O((M+N+K^2)*K)$$. 
Space Complexity: For each
c
, we only need the two extra deques and the result of the merge, which could up $$O(M + N + K)$$ space during their construction in the worst case, since the answer is not truncated until the end. Since $$K \leq M+N$$, this is order $$O(M+N)$$. Storing the answer also takes $$O(K)$$ space. In total, the space complexity is $$O(M + N)$$.
Approach #4: Annotated Greedy [Accepted & Optimal]
Intuition
The space of possible values in the array is small: there are only D = 10
of them. This suggests a weakness that can be exploited, by introducing a $$O(D)$$ factor into our algorithm.
Indeed, imagine we knew next1[i][d]
, the position of the next occurrence of digit d
in nums1
with index at least i
(and similarly for nums2
). Then, when thinking about the next value to write in our answer, we could brute force all $$D$$ possibilities. We know the next value we write has to be the largest d
such that we have enough digits left over to write k1
more digits.
Algorithm
Generate next1
and next2
annotations as described above, and denote the state (i, j, k)
as representing an instance of the problem where we have nums1[i:]
, nums2[j:]
, and we are writing the kth
digit. Let $$S_k$$ be the kth frontier: all our candidate states for a given k
.
Now, let us describe our frontier transition $$S_k \rightarrow S_{k+1}$$. For each d
, and each state $$S \in S_k$$, we will try to transition to a legal state  one where the number of digits remaining in nums1[i:]
and nums2[j:]
is enough. If we can, then for this d
, the set of these legal states will form our new frontier.
Additionally, when j1 < j2
, the state (i, j1, k)
dominates (i, j2, k)
. This means for a given i, k
, we only need to remember the lowest such j
seen.
This leads to the following solution.
class Solution(object):
def maxNumber(self, nums1, nums2, K):
INF = float('inf')
def remaining(i, j):
return len(nums1)  i + len(nums2)  j
def make_next(arr):
last = [INF] * 10
ans = [None] * len(arr)
for i in xrange(len(arr)  1, 1, 1):
last[arr[i]] = i
ans[i] = tuple(last)
return ans
next1 = make_next(nums1)
next2 = make_next(nums2)
frontier = {0: 0}
ans = [0] * K
for k in range(K):
new_frontier = {}
found = False
for d in range(9, 1, 1):
for i, j in frontier.items():
i2 = next1[i][d] if i < len(next1) else INF
j2 = next2[j][d] if j < len(next2) else INF
if remaining(i2, j) < K  k and remaining(i, j2) < K  k:
continue
ans[k] = d
found = True
for ci, cj in ((i2+1, j), (i, j2+1)):
if remaining(ci, cj) >= K  k  1:
new_frontier[ci] = min(new_frontier.get(ci, INF), cj)
if found: break
frontier = new_frontier
return ans
Complexity Analysis

Time Complexity: Let $$M, N$$ be the length of the given arrays, and $$K$$ the length of the desired final answer. Making the
next
arrays is $$O(M + N)$$ work. Our frontier is bounded in size bylen(M)
, and we do $$O(K)$$ work. In total, this is an $$O(MK + N)$$ solution. 
Space Complexity: Storing the
next
arrays took $$O(M + N)$$ space, while storing thefrontier
took $$O(M)$$ space. In total, $$O(M + N)$$ space was used.