hard +40 pts

Create Maximum Number

Merge two digit arrays to form the largest possible number of a given length.

Given two arrays of digits `nums1` and `nums2` (each element is a single digit 0-9), and an integer `k`, return an array of length `k` that contains the maximum number that can be formed by choosing digits from both arrays. The relative order of digits from the same original array must be preserved in the final number. You may choose any number of digits (including zero) from each array, but the total chosen must be exactly `k`. If it is impossible to choose exactly `k` digits, return an empty list. Implement the function `max_number(nums1, nums2, k)`. **Details:** - You can pick `i` digits from `nums1` and `k-i` digits from `nums2` for any valid `i` (0 ≤ i ≤ len(nums1), 0 ≤ k-i ≤ len(nums2)). - The resulting sequence must preserve the order of digits as they appear in each original array. - Among all possible valid selections, return the lexicographically largest (as a list of digits). - If no such `i` exists, return an empty list. Examples are provided below.

Constraints

- 0 ≤ nums1.length, nums2.length ≤ 100 - 0 ≤ k ≤ nums1.length + nums2.length - Each element in nums1 and nums2 is a digit 0-9. - Complexity: Aim for O((n+m)*k) or similar.

Example

```python
# Example 1
nums1 = [3, 4, 6, 5]
nums2 = [9, 1, 2, 5, 8, 3]
k = 5
# The largest number is [9, 8, 6, 5, 3]
print(max_number(nums1, nums2, k))  # [9, 8, 6, 5, 3]

# Example 2
nums1 = [6, 7]
nums2 = [6, 0, 4]
k = 5
# The largest number is [6, 7, 6, 0, 4]
print(max_number(nums1, nums2, k))  # [6, 7, 6, 0, 4]

# Example 3
nums1 = [3, 9]
nums2 = [8, 9]
k = 3
# The largest number is [9, 8, 9]
print(max_number(nums1, nums2, k))  # [9, 8, 9]
```
40 points ~35 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

For a fixed number of digits to take from nums1, how do you pick the maximum subsequence of that length from that array?
After choosing subsequences from both arrays, how do you merge them while preserving order and maximizing the result? (Think greedy comparison).
Try all possible splits i (digits from nums1) and k-i (digits from nums2), compute the best merge for each, and keep the overall maximum.
Use a stack-based greedy to find the maximum subsequence of given length from an array.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.