HardNo. 0321

Create Maximum Number — LeetCode 321 Python Solution

Pattern
Stack
Topics
Stack, Greedy, Array, Two Pointers, Monotonic Stack
Reading time
9 min

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

PythonSolution
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

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

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.

Related problems

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.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.