LeetCode 321: Create Maximum Number Solution in Python – A Step-by-Step Guide

What Is LeetCode 321: Create Maximum Number?

In LeetCode 321: Create Maximum Number, you’re given two integer arrays nums1 and nums2, and an integer k. Your task is to form a number of length k by selecting digits from nums1 and nums2, preserving their relative order within each array, and maximizing the resulting number. For example, with nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], and k = 5, the maximum number is [9,8,6,5,3]. This problem tests your ability to optimize selections, connecting to concepts in LeetCode 402: Remove K Digits.

Problem Statement

• Input: Two integer arrays nums1 and nums2, and an integer k.
• Output: An integer array of length k—the maximum number possible.
• Rules:
• Select digits from nums1 and nums2, maintaining relative order within each.
• Total length must be exactly k.
• Maximize the resulting number.

Constraints

• 1 <= nums1.length, nums2.length <= 500
• 0 <= nums1[i], nums2[i] <= 9
• 1 <= k <= nums1.length + nums2.length

Examples

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

Understanding the Problem: Building the Max Number

To solve LeetCode 321: Create Maximum Number in Python, we need to select k digits from nums1 and nums2, keeping their order, to form the largest possible number. A naive approach—trying all possible combinations—is O(2^(m+n)), where m and n are array lengths, far too slow. Instead, we’ll use:

• Best Solution (Greedy Merge): O(k * (m+n)) time, O(m+n) space—fast and practical.
• Alternative Solution (Dynamic Programming): O(k * m * n) time, O(k * m * n) space—thorough but complex.

Let’s start with the greedy merge solution, explained in a beginner-friendly way.

Best Solution: Greedy Merge Approach

Why This Is the Best Solution

The greedy merge approach is the top choice for LeetCode 321 because it’s efficient—O(k * (m+n)) time, O(m+n) space—and breaks the problem into manageable steps: greedily select the max subsequence from each array, then merge them optimally. It’s like picking the best digits step-by-step and stitching them together—smart and scalable!

How It Works

Think of this as a two-part strategy:

• Step 1: Max Subsequence:
• For each array, pick the largest possible subsequence of length i (0 ≤ i ≤ k) using a stack, dropping smaller digits when better ones follow.
• Step 2: Merge:
• Combine two subsequences (summing to k) by choosing the larger digit at each step, respecting order.
• Step 3: Maximize:
• Try all valid splits of k between the arrays, keep the best result.
• Step 4: Why It Works:
• Greedy selection ensures max subsequences.
• Merge compares optimally in lexicographical order.

It’s like crafting a number masterpiece—digit by digit!

Step-by-Step Example

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

• Max Subsequences:
• nums1: [3,4,6,5] → k=4: [3,4,6,5], k=3: [4,6,5], k=2: [6,5], k=1: [6]
• nums2: [9,1,2,5,8,3] → k=5: [9,2,5,8,3], k=4: [9,5,8,3], k=3: [9,8,3]
• Try Splits:
• 2 from nums1, 3 from nums2: [6,5] + [9,8,3] → Merge: [9,8,6,5,3]
• 3 from nums1, 2 from nums2: [4,6,5] + [9,8] → Merge: [9,8,4,6,5]
• Compare: [9,8,6,5,3] > [9,8,4,6,5]
• Result: [9,8,6,5,3]

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        def max_subsequence(nums, k):
            stack = []
            drop = len(nums) - k
            for num in nums:
                while drop > 0 and stack and stack[-1] < num:
                    stack.pop()
                    drop -= 1
                stack.append(num)
            return stack[:k] if len(stack) >= k else stack

        def merge(seq1, seq2):
            result = []
            i, j = 0, 0
            while i < len(seq1) and j < len(seq2):
                if seq1[i:] > seq2[j:]:  # Compare remaining parts
                    result.append(seq1[i])
                    i += 1
                else:
                    result.append(seq2[j])
                    j += 1
            result.extend(seq1[i:])
            result.extend(seq2[j:])
            return result

        m, n = len(nums1), len(nums2)
        max_result = [0] * k
        for i in range(max(0, k - n), min(k, m) + 1):
            sub1 = max_subsequence(nums1, i)
            sub2 = max_subsequence(nums2, k - i)
            candidate = merge(sub1, sub2)
            if candidate > max_result:
                max_result = candidate

        return max_result

• Lines 3-10: max_subsequence: Greedily build max subsequence of length k.
• Lines 12-22: merge: Combine two sequences, picking larger digits.
• Lines 25-30: Try all splits of k, update max result.
• Time Complexity: O(k * (m+n))—subsequence O(m+n), merge O(k), k iterations.
• Space Complexity: O(m+n)—subsequences and result.

This is like a number-crafting maestro—precise and quick!

Alternative Solution: Dynamic Programming Approach

Why an Alternative Approach?

The DP approach—O(k * m * n) time, O(k * m * n) space—builds the max number by considering all possible selections up to each position and length. It’s more thorough but slower and memory-heavy, offering a deeper understanding. It’s like exploring every numeric path—detailed and exhaustive!

How It Works

Build step-by-step:

• Step 1: DP table: dp[i][j][l] = max number of length l from nums1[:i] and nums2[:j].
• Step 2: Fill table with choices (use digit or skip).
• Step 3: Extract result from dp[m][n][k].

Step-by-Step Example

Example: nums1 = [3,4], nums2 = [5,6], k = 3

• DP States:
• dp[1][1][1]: [5], [4], [3]
• dp[2][2][3]: [5,6,4]
• Result: [5,6,4]

Code for DP Approach

Copy codeclass Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        m, n = len(nums1), len(nums2)
        dp = [[[""] * (k + 1) for _ in range(n + 1)] for _ in range(m + 1)]

        for i in range(m + 1):
            for j in range(n + 1):
                for l in range(k + 1):
                    if l == 0:
                        dp[i][j][l] = ""
                    elif i == 0 and j == 0:
                        continue
                    else:
                        candidates = []
                        if i > 0 and l <= i + j:
                            candidates.append(str(nums1[i-1]) + dp[i-1][j][l-1])
                        if j > 0 and l <= i + j:
                            candidates.append(str(nums2[j-1]) + dp[i][j-1][l-1])
                        if i > 0 and j > 0:
                            candidates.append(dp[i-1][j][l])
                            candidates.append(dp[i][j-1][l])
                        dp[i][j][l] = max(candidates or [""], key=lambda x: x.ljust(k, '0'))

        return [int(d) for d in dp[m][n][k]]

• Time Complexity: O(k * m * n)—fill DP table.
• Space Complexity: O(k * m * n)—table storage.

It’s a numeric pathfinder—comprehensive but heavy!

Comparing the Two Solutions

• Greedy Merge (Best):
• Pros: O(k * (m+n)) time, O(m+n) space, practical.
• Cons: Greedy logic trickier.
• DP (Alternative):
• Pros: O(k * m * n) time, O(k * m * n) space, exhaustive.
• Cons: Slower, memory-intensive.

Greedy wins for efficiency.

Additional Examples and Edge Cases

• [1], [2], 1: [2].
• [1,2], [3], 2: [3,2].
• [9], [8], 2: [9,8].

Both handle these well.

Complexity Breakdown

• Greedy Merge: Time O(k * (m+n)), Space O(m+n).
• DP: Time O(k * m * n), Space O(k * m * n).

Greedy is the clear choice.

Key Takeaways

• Greedy Merge: Smart selection—fast!
• DP: All paths covered—deep!
• Python: Lists and logic shine—see [Python Basics](/python/basics).
• Numbers: Order and greed combine.

Final Thoughts: Craft the Biggest Number

LeetCode 321: Create Maximum Number in Python is a numeric optimization thrill. The greedy merge solution offers speed and elegance, while DP provides a thorough alternative. Want more array challenges? Try LeetCode 402: Remove K Digits or LeetCode 300: Longest Increasing Subsequence. Ready to maximize? Head to Solve LeetCode 321 on LeetCode and build that number today!