Python solution with detailed explanation


  • 0
    G

    Solution

    Create Maximum Number https://leetcode.com/problems/create-maximum-number/

    Dynamic Programming/Recursive Solution

    • Sketch the recursion and throw in a cache. The complexity will be O(i * j * k).
    • The recursion is interesting in terms of the number of cases. When you have i,j, you need to think in how many different ways you can advance i and j with and without choosing nums1[i] and nums2[j]. Refer to the code, especially:
                self.max_number(i, j+1, k, nums1, nums2, so_far)            
                self.max_number(i+1, j, k, nums1, nums2, so_far)            
                self.max_number(i+1, j+1, k, nums1, nums2, so_far)
    
    class Solution(object):
        def max_number(self, i, j, k, nums1, nums2, so_far):
            if len(so_far) == k:
                int_number = int("".join(map(str, so_far)))
                if int_number > self.maximum_number:
                    self.maximum_number = int_number
                    self.max_list = [x for x in so_far]
            elif 0<=i<len(nums1) and 0<=j<len(nums2):
                if nums1[i] > nums2[j]:
                    so_far.append(nums1[i])
                    self.max_number(i+1, j, k, nums1, nums2, so_far)
                    so_far.pop()
                elif nums1[i] < nums2[j]:
                    so_far.append(nums2[j])
                    self.max_number(i, j+1, k, nums1, nums2, so_far)
                    so_far.pop()
                elif nums1[i] == nums2[j]:
                    so_far.append(nums1[i])
                    self.max_number(i+1, j, k, nums1, nums2, so_far)
                    so_far.pop()                
                    so_far.append(nums2[j])
                    self.max_number(i, j+1, k, nums1, nums2, so_far)
                    so_far.pop()
                # Ignore nums[i]    
                self.max_number(i, j+1, k, nums1, nums2, so_far)
                # ignore nums[i]
                self.max_number(i+1, j, k, nums1, nums2, so_far)
                # Ignore both
                self.max_number(i+1, j+1, k, nums1, nums2, so_far)
            elif i == len(nums1) and 0<=j<len(nums2):
                so_far.append(nums2[j])
                self.max_number(i, j+1, k, nums1, nums2, so_far)
                so_far.pop()
                self.max_number(i, j+1, k, nums1, nums2, so_far)
            elif j == len(nums2) and 0<=i<len(nums1):
                so_far.append(nums1[i])
                self.max_number(i+1, j, k, nums1, nums2, so_far)
                so_far.pop()
                self.max_number(i+1, j, k, nums1, nums2, so_far)
            return
        
        def maxNumber(self, nums1, nums2, k):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :type k: int
            :rtype: List[int]
            """
            N, M = len(nums1), len(nums2)
            self.maximum_number, self.max_list = -2**31, None
            self.max_number(0, 0, k, nums1, nums2, [])
            return self.max_list
    

    Optimized Solution using Stacks

    • There is a smarter solution to this problem which is a combination of 2 smaller problems.
    • The solution to this problem will comprise of k digits, i from nums1 and k-i from nums2.
    • Assume i were 2, then what would be the best candidate? Clearly, the answer is "maximum number of size 2 from nums1 while keeping the relative order of the digits".
    • So lets call that problem as P0: "Given an array nums and an integer n, return the maximum number of size n that can be formed from nums while keeping the relative order of digits". Now for i=2, we will have 2 lists from nums1 and nums2 of size i and K-1.
    • We can merge them to compute a candidate solution of size k. This will be problem P1
    • What can be all the possible candidate solutions? Clearly when i will range from 0 to K for nums1 we will have a corresponding pair from nums2 ranging in size K to 0. Merging each of these pairs will give us the K+1 candidates. We then choose the largest from this pool and we are done!
      https://discuss.leetcode.com/topic/32281/share-my-python-solution-with-explanation

    P1: Merge 2 arrays with size i and K-1 formed from nums1 and nums2 to return the maximum possible number array of size K.

    • This is just like merge-sort merging, except when the elements are same. In that case we need to look beyond the current element (skipping all equal elements) to find the first unequal element and then pick the one which has the higher unequal element. Notice that when nums1[i] (or nums2[j]) is the last element and the value is equal to nums2[j] (or nums1[i]), we always pick the from the sublist which has elements remaining since there is a possibility of finding a greater solution.
                    x,y = i, j
                    while x < N and y < M and left[x] == right[y]:
                        x,y = x+1, y+1
                    if x != N and y != M and left[x] > right[y]:
                        result.append(left[i])
                        i += 1
                    elif x != N and y != M and left[x] < right[y]:
                        result.append(right[j])
                        j += 1
                    elif x == N:
                        result.append(right[j])
                        j += 1
                    elif y == M:
                        result.append(left[i])
                        i += 1
    
    • Notice that in Python we can compare 2 lists l1 > l2 (merge_solution function) which does the above.
     if nums1 > nums2:
                    ans += nums1[0],
    

    P0: Given an array nums and an integer n, return the maximum number of size n that can be formed from nums while keeping the relative order of digits.

    Method 1

    • We can maintain a stack. As long as we get input in descending order, just keep pushing on the stack. if you get a number larger than top of stack, then pop till you find a smaller number.While doing this, make sure you do not pop so much that you cannot meet the constraint of K digits. Refer to the code in max_number_list.

    Method 2

    • Say the size of array is N = 10. Say K = 6. What is the maximum number that can be formed of size N = 10? Answer is the original array. What about K = 6?
    • This problem can be stated as: "Remove k1 (4) digits from the array to form the largest number". This is the opposite of https://leetcode.com/problems/remove-k-digits/ where we remove K digits to form the smallest number
    • The solution to the smallest number problem was to scan from left to right and remove the first peak element and then the next peak from the solution of previous.
    • The solution to this problem is opposite - remove the first trough element, i.e. element which is smaller than both its left and right side!
    class Solution(object):
        def max_number_list(self, nums, n):
            st, required_to_remove = [], len(nums)-n
            for idx, x in enumerate(nums):
                while required_to_remove and st and st[-1] < x:
                    st.pop()
                    required_to_remove = required_to_remove - 1
                st.append(x)
            while len(st) > n:
                st.pop()
            return st
        
        def merge(self, left, right):
            i, j = 0, 0
            N, M = len(left), len(right)
            result = []
            while i < N or j < M:
                if i == N:
                    result.append(right[j])
                    j += 1
                elif j == M:
                    result.append(left[i])
                    i += 1
                elif left[i] < right[j]:
                    result.append(right[j])
                    j += 1
                elif left[i] > right[j]:
                    result.append(left[i])
                    i += 1
                else:
                    x,y = i, j
                    while x < N and y < M and left[x] == right[y]:
                        x,y = x+1, y+1
                    if x != N and y != M and left[x] > right[y]:
                        result.append(left[i])
                        i += 1
                    elif x != N and y != M and left[x] < right[y]:
                        result.append(right[j])
                        j += 1
                    elif x == N:
                        result.append(right[j])
                        j += 1
                    elif y == M:
                        result.append(left[i])
                        i += 1
            return result
    
        def merge_solution(self, nums1, nums2):
            ans = []
            while nums1 or nums2:
                if nums1 > nums2:
                    ans += nums1[0],
                    nums1 = nums1[1:]
                else:
                    ans += nums2[0],
                    nums2 = nums2[1:]
            return ans
    
        def maxNumber(self, nums1, nums2, k):
            """
            :type nums1: List[int]
            :type nums2: List[int]
            :type k: int
            :rtype: List[int]
            """
            N, M = len(nums1), len(nums2)
            self.max_list = [0]*k
            for i in range(k+1):
                if i <= N and k-i <= M:
                    left, right = self.max_number_list(nums1, i), self.max_number_list(nums2, k-i)
                    merged = self.merge(left, right)
                    for i in range(k):
                        if self.max_list[i] != merged[i]:
                            if self.max_list[i] > merged[i]:
                                break
                            elif merged[i] > self.max_list[i]:
                                self.max_list = merged
                                break
            return self.max_list
    

Log in to reply
 

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