Show problems as
Classic problem #321HardArrayTwo PointersStackGreedyMonotonic Stack

Create Maximum Number

Real-world version: The Largest Reading From Two Tapes
Tracked in this browser only
Read Create Maximum Number on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Two tapes of single digits read first and second. Choose k digits altogether, some from each tape, keeping the digits of each tape in the order they appear on it, and read the chosen digits off as one number of k digits.

Return the largest number obtainable, as the list of its k digits.

Examples

Example 1

Input
first = [8, 6, 9], second = [1, 7, 5], k = 3
Output
[9, 7, 5]

Three digits in all. Taking 8 and 9 from the first tape and 7 from the second, then merging them, reads 987. Nothing larger is available, since the only 9 sits at the end of the first tape and reaching it costs the 6 in front of it.

Example 2

Input
first = [9, 9, 9], second = [1, 1, 1], k = 3
Output
[9, 9, 9]

The first tape holds three nines, which beats anything the second tape could contribute, so all three digits come from there.

Example 3

Input
first = [1], second = [2], k = 2
Output
[2, 1]

Both digits are needed, and putting the larger one first reads 21.

Constraints

  • 1 <= first.length <= 500
  • 1 <= second.length <= 500
  • 0 <= first[i] <= 9
  • 0 <= second[i] <= 9
  • 1 <= k <= first.length + second.length

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def max_number(first: list[int], second: list[int], k: int) -> list[int]:
Java
public int[] maxNumber(int[] first, int[] second, int k)

More on the same topics