How hard is LeetCode 321. Create Maximum Number?

LeetCode 321. Create Maximum Number is rated Hard on LeetCode.

What is the time complexity of LeetCode 321. Create Maximum Number?

The Python solution on this page runs in O(n) (after optional sort O(n log n)).

What is the space complexity of LeetCode 321. Create Maximum Number?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 321. Create Maximum Number cover?

LeetCode 321. Create Maximum Number is tagged Stack, Greedy, Array, Two Pointers and Monotonic Stack on LeetCode.

Create Maximum Number — LeetCode 321 Python Solution

HardStackGreedyArrayTwo PointersMonotonic Stack

Problem: #321
Pattern: Stack
Reading time: 9 min
Source: leetcode.com

The problem

You are given two integer arrays nums1 and nums2 of lengths m and n respectively. nums1 and nums2 represent the digits of two numbers.

Example

Input: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5
Output: [9,8,6,5,3]

Python solution

Python

class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        def f(nums: List[int], k: int) -> List[int]:
            n = len(nums)
            stk = [0] * k
            top = -1
            remain = n - k
            for x in nums:
                while top >= 0 and stk[top] < x and remain > 0:
                    top -= 1
                    remain -= 1
                if top + 1 < k:
                    top += 1
                    stk[top] = x
                else:
                    remain -= 1
            return stk

        def compare(nums1: List[int], nums2: List[int], i: int, j: int) -> bool:
            if i >= len(nums1):
                return False
            if j >= len(nums2):
                return True
            if nums1[i] > nums2[j]:
                return True
            if nums1[i] < nums2[j]:
                return False
            return compare(nums1, nums2, i + 1, j + 1)

        def merge(nums1: List[int], nums2: List[int]) -> List[int]:
            m, n = len(nums1), len(nums2)
            i = j = 0
            ans = [0] * (m + n)
            for k in range(m + n):
                if compare(nums1, nums2, i, j):
                    ans[k] = nums1[i]
                    i += 1
                else:
                    ans[k] = nums2[j]
                    j += 1
            return ans

        m, n = len(nums1), len(nums2)
        l, r = max(0, k - n), min(k, m)
        ans = [0] * k
        for x in range(l, r + 1):
            arr1 = f(nums1, x)
            arr2 = f(nums2, k - x)
            arr = merge(arr1, arr2)
            if ans < arr:
                ans = arr
        return ans

Complexity

Measure	Complexity
Time	O(n) (after optional sort O(n log n))
Space	O(1) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 321. Create Maximum Number is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 321. Create Maximum Number?: LeetCode 321. Create Maximum Number is rated Hard on LeetCode.
What is the time complexity of LeetCode 321. Create Maximum Number?: The Python solution on this page runs in O(n) (after optional sort O(n log n)).
What is the space complexity of LeetCode 321. Create Maximum Number?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 321. Create Maximum Number cover?: LeetCode 321. Create Maximum Number is tagged Stack, Greedy, Array, Two Pointers and Monotonic Stack on LeetCode.