Problem statement

https://leetcode.com/problems/create-maximum-number/

Solution 1

Let N1 and N2 be lengths of nums1 and nums2. First solution we can think about is dp, where dp[i1][i2][i3] is maximum number, using first i1 digits from nums, i2 digits from nums2 and have i3 digits so far. To evaluate dp[i1][i2][3], we need to consider dp[i1-1][i2][i3-1] * 10 + nums1[i1], if we take the last digit from nums1[:i1] or dp[i1-1][i2][i3]` of if we do not taeke it. Similar 2 cases for the second number.

Complexity

To compare this numbers we need O(k) time, so overall complexity is O(N1 N2 k^2), unfortunatelly it will give TLE.

Code

class Solution:
    def maxNumber(self, nums1, nums2, k):
        nums1 = "".join(str(i) for i in nums1)
        nums2 = "".join(str(i) for i in nums2)
        
        @lru_cache(None)
        def dp(i1, i2, i3):
            if i1 == -1 and i2 == -1:
                return "" if i3 == 0 else "!"
            cands = []     
            if i1 >= 0: cands += [dp(i1-1, i2, i3-1) + nums1[i1], dp(i1-1, i2, i3)]
            if i2 >= 0: cands += [dp(i1, i2-1, i3-1) + nums2[i2], dp(i1, i2-1, i3)]
            return max([c for c in cands if not c or c[0] != "!"] or ["!"])
        
        t = dp(len(nums1) - 1, len(nums2) - 1, k)
        return [int(i) for i in str(t)]

Solution 2

There is another, better solution. Let us take i digits from first number and k-i digits from second number. How we can choose i digits, so number will be the biggest? We do it in greedy way, similar to Problem 0402, using monotonic stack. We iterate over nums1 and before we put digit to stack, we remove as much digits from stack as possible, so that the beginning of number is increased: while stack and int(digit) < int(stack[-1]) and attempts > 0, where attempts is how much digits we need to remove at the end. So, we construct maximum numbers for nums1 and nums2 in O(N1 + N2) for every i, and then we need to merge two numbers into one big number. We can do it in O((N1 + N2)^2): compare numbers and choose the first digit of the biggest one, remove this digit from original number and continue. It is not O(N1 + N2), because each time we need to compare full numbers, not only first digits: the question is what to do if we have to equal digits: we need to look into next digit and so on. So, overall complexity is O(k(N1 + N2)^2). I think it is doable in O(k(N1 + N2)) as well, but it is very difficult.

Complexity

It is O(k(N1 + N2)^2) for time and O(N1 + N2) for space.

Code

class Solution:
    def maxNumber(self, nums1, nums2, k):
        def max_num(nums, T):
            attempts = len(nums) - T
            stack = []
            for num in nums:
                while stack and num > stack[-1] and attempts > 0:
                    stack.pop()
                    attempts -= 1
                stack.append(num)
            return stack[:T]
        
        ans = []
        
        for i in range(k + 1):
            N1 = max_num(nums1, i)
            N2 = max_num(nums2, k-i)
            cand = []
            if len(N1) + len(N2) != k: continue
            
            while N1 or N2:
                if N1 < N2: N1, N2 = N2, N1
                cand.append(N1.pop(0))
            
            ans = max(cand, ans)
            
        return ans