# LeetCode 321: Create Maximum Number

## Problem Restatement

We are given two arrays of digits:

```python
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

| Item | Meaning |
|---|---|
| Input | Digit arrays `nums1`, `nums2`, and integer `k` |
| Output | Maximum length-`k` digit array |
| Constraint | Relative order inside each original array must be preserved |
| Digits | Each value is from `0` to `9` |

Function shape:

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

## Examples

Example 1:

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

Output:

```python
[9, 8, 6, 5, 3]
```

One optimal choice is:

| Source | Chosen digits |
|---|---|
| `nums1` | `[6, 5]` |
| `nums2` | `[9, 8, 3]` |

Merged together:

```python
[9, 8, 6, 5, 3]
```

Example 2:

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

We must take all digits.

Output:

```python
[6, 7, 6, 0, 4]
```

Example 3:

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

Output:

```python
[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:

```python
i
```

digits from `nums1`.

Then we must take:

```python
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:

```python
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:

```python
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:

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

We can drop `2` digits.

Process `3`, stack is:

```python
[3]
```

Process `4`.

Since `4 > 3`, pop `3`.

```python
[4]
```

Process `6`.

Since `6 > 4`, pop `4`.

```python
[6]
```

Process `5`.

Push it.

```python
[6, 5]
```

Best length-`2` subsequence:

```python
[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:

```python
seq1[i:] > seq2[j:]
```

take from `seq1`.

Otherwise, take from `seq2`.

Why compare suffixes instead of only current digits?

Because ties matter.

Example:

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

Both start with `6`.

If we only compare current digits, we cannot decide.

Compare suffixes:

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

because after the first equal `6`, `7 > 0`.

So we should take from `seq1` first.

That gives:

```python
[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:

| Symbol | Meaning |
|---|---|
| `m` | Length of `nums1` |
| `n` | Length of `nums2` |
| `k` | Required output length |

| Metric | Value | Why |
|---|---:|---|
| Time | `O(k^2(m + n))` | Up to `k + 1` splits; suffix comparisons during merge can cost up to `O(k)` |
| Space | `O(m + n + k)` | Subsequence stacks and merged result |

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

## Implementation

```python
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.

```python
drop = len(nums) - size
```

This is how many digits may be removed.

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

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

Then we push the current digit.

```python
stack.append(num)
```

At the end, return only the required length.

```python
return stack[:size]
```

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

The `greater` helper compares suffixes:

```python
greater(a, i, b, j)
```

It skips equal digits.

```python
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.

```python
if j == len(b):
    return True
```

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

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

The merge uses this comparison at every step.

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

The split range is:

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

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

```python
if candidate > best:
    best = candidate
```

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

## Testing

```python
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:

| Test | Why |
|---|---|
| Standard example | Main greedy split case |
| Must take all digits | Checks merge tie behavior |
| `[3,9]`, `[8,9]` | Confirms valid split choice |
| Swapped arrays | Confirms source order handling |
| Equal leading digits | Checks suffix comparison |
| `k = m + n` | Must merge all digits correctly |