LeetCode 321: Create Maximum Number

Problem Description

LeetCode Problem 321

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

Create the maximum number of length k <= m + n from digits of the two numbers. The relative order of the digits from the same array must be preserved.

Return an array of the k digits representing the answer.

Example 1:

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

Example 2:

Input: nums1 = [6,7], nums2 = [6,0,4], k = 5
Output: [6,7,6,0,4]

Example 3:

Input: nums1 = [3,9], nums2 = [8,9], k = 3
Output: [9,8,9]

Constraints:

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

Difficulty: Hard

Tags: array, two pointers, stack, greedy, monotonic stack

Rating: 84.73%

Solution

The solution can be broken down into three main components:

1. Finding maximum subsequences of given length from individual arrays
2. Merging two subsequences optimally
3. Trying all possible combinations of lengths from both arrays that sum to k

Component 1: Maximum Subsequence (maxArray function)

def maxArray(nums, t):
    stack = []
    to_pop = len(nums)-t
    for n in nums:
        while stack and stack[-1] < n and to_pop > 0:
            stack.pop()
            to_pop -= 1
        stack.append(n)
    return stack[:t]

This function uses a monotonic stack approach to find the maximum subsequence of length t. Here’s how it works:

1. We maintain a stack of digits that will form our subsequence
2. For each number, we can pop existing numbers from the stack if:
   • The current number is larger than the top of the stack
   • We still have enough numbers left to form a sequence of length t
3. The variable to_pop keeps track of how many numbers we can still remove while ensuring we’ll have enough digits

Example:

nums = [4,2,5,3,1], t = 3
Process:
- Start: stack = []
- 4: stack = [4]
- 2: stack = [4,2]
- 5: pop 4,2 (both smaller), stack = [5]
- 3: stack = [5,3]
- 1: stack = [5,3,1]
Result: [5,3,1]

Component 2: Merging Subsequences (merge function)

def merge(arr1, arr2):
    res = []
    while arr1 or arr2:
        if arr1 > arr2:
            res.append(arr1[0])
            arr1 = arr1[1:]
        else:
            res.append(arr2[0])
            arr2 = arr2[1:]
    return res

The merge function combines two subsequences to create the maximum possible number. The key insight is that we need to compare entire remaining subsequences, not just the first digits. This is because:

• If we have arr1 = [6,7] and arr2 = [6,0,4]
• At first position, both have 6
• We need to look ahead: [7] > [0,4], so we should take 6 from arr1

The comparison arr1 > arr2 uses Python’s lexicographical comparison, which is exactly what we need here.

Component 3: Main Algorithm

max_num = []
for i in range(max(0, k-n), min(k+1, m+1)):
    j = k - i
    candidate = merge(maxArray(nums1, i), maxArray(nums2, j))
    max_num = max(max_num, candidate)
return max_num

The main algorithm tries all valid combinations of taking i elements from nums1 and (k-i) elements from nums2. For each combination:

1. Extract maximum subsequence of length i from nums1
2. Extract maximum subsequence of length (k-i) from nums2
3. Merge these subsequences
4. Keep track of the maximum result seen so far

The range for i is carefully chosen:

• Lower bound: max(0, k-n) ensures we don’t try to take more elements from nums2 than available
• Upper bound: min(k+1, m+1) ensures we don’t try to take more elements from nums1 than available

Time Complexity Analysis

The overall time complexity is $O(k × (m+n)²)$:

• Finding maximum subsequence: $O(n)$
• Merging subsequences: $O(k)$
• Number of combinations to try: $O(k)$

Space complexity is $O(k)$ for storing the result and intermediate subsequences.

Example Walkthrough

Let’s walk through Example 1: nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5

1. Try different combinations of lengths:

   • i=0, j=5: Take 5 from nums2 → [9,2,5,8,3]
   • i=1, j=4: Combine max(nums1,1) and max(nums2,4) → [9,8,6,5,3]
   • i=2, j=3: …
   • and so on

2. The maximum result is [9,8,6,5,3], achieved by:

   • Taking [6] from nums1 (maxArray)
   • Taking [9,8,5,3] from nums2 (maxArray)
   • Merging them optimally

This example demonstrates how the algorithm considers all possibilities to find the global maximum.