Create Maximum Number

Question

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]

Tags

• Dynamic Programming
• Stack
• Greedy

Thought

Reference: https://discuss.leetcode.com/topic/32298/short-python-ruby-c

Compare to the previous problem, it requires the implementation of dynamic programming during the process because there are two lists need to be compared.

But the idea is straightforward:

1. Build the DP array such that store all the possible combinations
2. Preprocess the lists by removing some digits according to k value.
3. merge the two lists to form an item in the DP array.
4. Find the maximum value of DP array.

Code

class Solution(object):
    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[int]
        """
        def preprocess(nums, k):
            stack = []
            drop = len(nums) - k
            for ch in nums:
                while drop > 0 and stack and stack[-1] < ch:
                    stack.pop()
                    drop -= 1
                stack.append(ch)
            return stack[:k]

        def merge(num1, num2):
            return [max(num1, num2).pop(0) for _ in num1 + num2]

        result = []
        for i in xrange(k + 1):
            if i <= len(nums1) and k - i <= len(nums2):
                result.append(merge(preprocess(nums1, i), preprocess(nums2, k - i)))
        return max(result)