LeetCode 321: Create Maximum Number

Problem Restatement

We are given two arrays of digits:

nums1
nums2

They represent two numbers.

We are also given an integer k.

We need to create the maximum possible number of length k by taking digits from the two arrays.

Rules:

1. We may take digits from both arrays.
2. We must take exactly k digits total.
3. The relative order of digits taken from the same array must be preserved.
4. Return the answer as an array of digits.

The official constraints include 1 <= m, n <= 500, 0 <= nums1[i], nums2[i] <= 9, and 1 <= k <= m + n. The examples include nums1 = [3,4,6,5], nums2 = [9,1,2,5,8,3], k = 5, whose output is [9,8,6,5,3].

Input and Output

Function shape:

def maxNumber(
    nums1: list[int],
    nums2: list[int],
    k: int,
) -> list[int]:
    ...

Examples

Example 1:

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

Output:

[9, 8, 6, 5, 3]

One optimal choice is:

Merged together:

[9, 8, 6, 5, 3]

Example 2:

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

We must take all digits.

Output:

[6, 7, 6, 0, 4]

Example 3:

nums1 = [3, 9]
nums2 = [8, 9]
k = 3

Output:

[9, 8, 9]

First Thought: Try All Choices

We could try every way to choose some digits from nums1 and some digits from nums2.

Then merge them in every possible way.

This is too large.

Even choosing subsequences from one array can create many possibilities.

We need to split the problem into smaller greedy subproblems.

Key Insight

Suppose we decide to take:

i

digits from nums1.

Then we must take:

k - i

digits from nums2.

For that fixed split, the best answer must use:

1. The largest subsequence of length i from nums1.
2. The largest subsequence of length k - i from nums2.
3. The best merge of those two subsequences.

Then we try every valid split and keep the best result.

The valid range for i is:

max(0, k - len(nums2)) <= i <= min(k, len(nums1))

This ensures neither array is asked to provide more digits than it has.

Subproblem 1: Maximum Subsequence of Fixed Length

Given one array, choose exactly t digits while preserving order.

We want the lexicographically largest result.

Use a monotonic decreasing stack.

Let:

drop = len(nums) - t

This is how many digits we are allowed to remove.

For each digit:

1. While the stack is not empty,
2. and the top digit is smaller than the current digit,
3. and we still can drop digits,
4. pop the stack.

Then push the current digit.

At the end, return the first t digits of the stack.

Example:

nums = [3, 4, 6, 5]
t = 2

We can drop 2 digits.

Process 3, stack is:

[3]

Process 4.

Since 4 > 3, pop 3.

[4]

Process 6.

Since 6 > 4, pop 4.

[6]

Process 5.

Push it.

[6, 5]

Best length-2 subsequence:

[6, 5]

Subproblem 2: Merge Two Subsequences

Given two subsequences, merge them into the largest possible result.

At each step, compare the remaining suffixes.

If:

seq1[i:] > seq2[j:]

take from seq1.

Otherwise, take from seq2.

Why compare suffixes instead of only current digits?

Because ties matter.

Example:

seq1 = [6, 7]
seq2 = [6, 0, 4]

Both start with 6.

If we only compare current digits, we cannot decide.

Compare suffixes:

[6, 7] > [6, 0, 4]

because after the first equal 6, 7 > 0.

So we should take from seq1 first.

That gives:

[6, 7, 6, 0, 4]

Algorithm

1. Let m = len(nums1) and n = len(nums2).
2. Initialize best = [].
3. For every valid number i of digits taken from nums1:
   • Take i digits from nums1 using monotonic stack.
   • Take k - i digits from nums2 using monotonic stack.
   • Merge the two subsequences greedily.
   • If the merged result is larger than best, update best.
4. Return best.

Correctness

For any optimal answer, suppose it takes i digits from nums1 and k - i digits from nums2.

Among all length-i subsequences of nums1, replacing the chosen subsequence with the maximum length-i subsequence can only make the final merged number larger or equal. The same applies to the length-k-i subsequence from nums2.

So for each fixed split, it is enough to consider the maximum subsequence from each array.

Now consider merging two fixed subsequences. At each position, if the remaining suffix of the first subsequence is lexicographically larger than the remaining suffix of the second, choosing from the first gives the best possible next digit sequence. If the second suffix is larger or equal, choosing from the second is at least as good. This greedy choice fixes the earliest differing position as large as possible.

The algorithm tries every valid split. Since the optimal answer uses one of those splits, and the algorithm computes the best result for each split, the maximum over all splits is the global optimum.

Therefore, the algorithm returns the maximum possible number of length k.

Complexity

Let:

With m, n <= 500, this approach is acceptable.

Implementation

class Solution:
    def maxNumber(
        self,
        nums1: list[int],
        nums2: list[int],
        k: int,
    ) -> list[int]:

        def max_subsequence(nums: list[int], size: int) -> list[int]:
            drop = len(nums) - size
            stack = []

            for num in nums:
                while stack and drop > 0 and stack[-1] < num:
                    stack.pop()
                    drop -= 1

                stack.append(num)

            return stack[:size]

        def greater(
            a: list[int],
            i: int,
            b: list[int],
            j: int,
        ) -> bool:
            while i < len(a) and j < len(b) and a[i] == b[j]:
                i += 1
                j += 1

            if j == len(b):
                return True

            if i < len(a) and a[i] > b[j]:
                return True

            return False

        def merge(a: list[int], b: list[int]) -> list[int]:
            i = 0
            j = 0
            result = []

            while i < len(a) or j < len(b):
                if greater(a, i, b, j):
                    result.append(a[i])
                    i += 1
                else:
                    result.append(b[j])
                    j += 1

            return result

        m = len(nums1)
        n = len(nums2)

        best = []

        start = max(0, k - n)
        end = min(k, m)

        for take1 in range(start, end + 1):
            take2 = k - take1

            part1 = max_subsequence(nums1, take1)
            part2 = max_subsequence(nums2, take2)

            candidate = merge(part1, part2)

            if candidate > best:
                best = candidate

        return best

Code Explanation

The helper max_subsequence chooses the largest subsequence of a fixed size.

drop = len(nums) - size

This is how many digits may be removed.

When a larger digit appears, we remove smaller previous digits if possible.

while stack and drop > 0 and stack[-1] < num:
    stack.pop()
    drop -= 1

Then we push the current digit.

stack.append(num)

At the end, return only the required length.

return stack[:size]

This matters when the stack still has extra digits because not all allowed drops were used.

The greater helper compares suffixes:

greater(a, i, b, j)

It skips equal digits.

while i < len(a) and j < len(b) and a[i] == b[j]:
    i += 1
    j += 1

If b is exhausted, then a is better or equal.

if j == len(b):
    return True

Otherwise, a is better only if its next differing digit is larger.

if i < len(a) and a[i] > b[j]:
    return True

The merge uses this comparison at every step.

if greater(a, i, b, j):
    result.append(a[i])
    i += 1
else:
    result.append(b[j])
    j += 1

The split range is:

start = max(0, k - n)
end = min(k, m)

For each split, build the best candidate and update the answer.

if candidate > best:
    best = candidate

Python lists compare lexicographically, which matches digit-array comparison.

Testing

def run_tests():
    s = Solution()

    assert s.maxNumber(
        [3, 4, 6, 5],
        [9, 1, 2, 5, 8, 3],
        5,
    ) == [9, 8, 6, 5, 3]

    assert s.maxNumber(
        [6, 7],
        [6, 0, 4],
        5,
    ) == [6, 7, 6, 0, 4]

    assert s.maxNumber(
        [3, 9],
        [8, 9],
        3,
    ) == [9, 8, 9]

    assert s.maxNumber(
        [9, 1, 2, 5, 8, 3],
        [3, 4, 6, 5],
        5,
    ) == [9, 8, 6, 5, 3]

    assert s.maxNumber(
        [6, 6],
        [6],
        2,
    ) == [6, 6]

    assert s.maxNumber(
        [2, 5, 6, 4, 4, 0],
        [7, 3, 8, 0, 6, 5, 7, 6, 2],
        15,
    ) == [7, 3, 8, 2, 5, 6, 4, 4, 0, 6, 5, 7, 6, 2]

    print("all tests passed")

run_tests()

Test meaning: