1026HardArrayTwo PointersStackGreedyMonotonic Stack

The Largest Reading From Two Tapes

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a 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)

The intended approach

Time O(k * (m + n) + k^3) at worst, for tapes of length m and n: a stack pass per split, and a merge whose tie-breaking may scan ahead.Space O(k) for the chosen sequences and the answer.

Split the job by how many digits come off each tape. For a fixed split, the best reading is the best merge of the best digits that many from one tape and the rest from the other, because the two choices never constrain one another. Best so many digits from one tape, order kept: walk the tape with a stack. Before pushing a digit, pop any digit already on the stack that is smaller, so long as enough digits remain further along to still reach the wanted count. That leaves the largest possible sequence, since a smaller digit sitting earlier is always worth dropping when something larger can take its place and the count can still be met. Merging two chosen sequences: take from whichever has the larger digit at its front, and where the fronts tie, look further along both until they differ and take from the one that reads larger. That tie rule matters; taking from the wrong side can strand a small digit in a high place. Then compare the candidate readings over all the splits and keep the largest. There are at most one more split than `k`, so the whole thing stays manageable, though the tie-breaking during a merge can scan ahead and that is where the worst case lives.

Pythonentry point: max_number

def max_number(first, second, k):
    def best(tape, want):
        if want == 0:
            return []
        drop = len(tape) - want
        stack = []
        for digit in tape:
            while drop and stack and stack[len(stack) - 1] < digit:
                stack.pop()
                drop -= 1
            stack.append(digit)
        return stack[:want]
    def take_first(a, i, b, j):
        while i < len(a) and j < len(b):
            if a[i] != b[j]:
                return a[i] > b[j]
            i += 1
            j += 1
        return j >= len(b)
    def merge(a, b):
        out = []
        i = 0
        j = 0
        while i < len(a) or j < len(b):
            if take_first(a, i, b, j):
                out.append(a[i])
                i += 1
            else:
                out.append(b[j])
                j += 1
        return out
    lo = 0 if k <= len(second) else k - len(second)
    hi = k if k <= len(first) else len(first)
    answer = None
    for take in range(lo, hi + 1):
        candidate = merge(best(first, take), best(second, k - take))
        if answer is None or candidate > answer:
            answer = candidate
    return answer if answer is not None else []

The obvious version

Search the two tapes outright. From a position on each tape and a number of digits still wanted, either take the digit under one of the two heads or step past it, and keep whichever choice leads to the larger reading. Remember the answer for each position so it is worked out once. Costs a stored reading per position rather than a stack pass and a merge.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_number(first, second, k):
    m = len(first)
    n = len(second)
    memo = {}
    def best(i, j, need):
        if need == 0:
            return ()
        if m - i + n - j < need:
            return None
        key = (i, j, need)
        if key in memo:
            return memo[key]
        answer = None
        if i < m:
            tail = best(i + 1, j, need - 1)
            if tail is not None:
                got = (first[i],) + tail
                if answer is None or got > answer:
                    answer = got
            tail = best(i + 1, j, need)
            if tail is not None and (answer is None or tail > answer):
                answer = tail
        if j < n:
            tail = best(i, j + 1, need - 1)
            if tail is not None:
                got = (second[j],) + tail
                if answer is None or got > answer:
                    answer = got
            tail = best(i, j + 1, need)
            if tail is not None and (answer is None or tail > answer):
                answer = tail
        memo[key] = answer
        return answer
    got = best(0, 0, k)
    return list(got) if got is not None else []

How this problem was checked

Reference solution executed against 18 test cases — 18 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in