Solution by awice


  • 0

    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, k-1)
            if nums2:
                cand2 = self.maxNumber(nums1, nums2[1:], k)
                cand3 = [nums2[0]] + self.maxNumber(nums1, nums2[1:], k-1)
    
            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 complexity-bound 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, k-1)
                        if j < len(nums2):
                            cand2 = dp(i, j+1, k)
                            cand3 = [nums2[j]] + dp(i, j+1, k-1)
    
                        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 k-c 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 k-c <= len(nums2):
                    cand = merge(best(nums1, c), best(nums2, k-c))
                    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 and merge. For each c, our calls to best are order $$O(M) + O(N) = O(M+N)$$, and our call to merge is $$O(K^2)$$ in the worst case, as in our comparison step we may need to make element-wise 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 k-1 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 k-th digit. Let $$S_k$$ be the k-th 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 by len(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 the frontier took $$O(M)$$ space. In total, $$O(M + N)$$ space was used.


Log in to reply
 

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