0036EasyArrayTwo PointersSorting

Merge Into the Padded Log

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 probes each wrote down signed temperature deltas, and both wrote them in non-decreasing order. The station keeps one long log, the integer array base, which was sized up front to hold both probes' output: its first filled positions carry the deltas the station probe recorded, and the added positions after them are reserve slots. A reserve slot is stored as 0 and carries no reading, so any value you find there is free to overwrite.

The second probe's added deltas arrive in the integer array patch, also in non-decreasing order.

Fold patch into base so that base ends up carrying all filled + added deltas in non-decreasing order. Do it inside base, using no more than a constant amount of extra space, then return base. Note that a delta of 0 is a perfectly ordinary reading, so a position cannot be judged by its value alone; only filled says where the real readings stop.

Examples

Example 1

Input: base = [-4, 2, 7, 0, 0], filled = 3, patch = [1, 9], added = 2
Output: [-4, 1, 2, 7, 9]

The two reserve slots at the end make room for 1 and 9, which slot in around the existing deltas.

Example 2

Input: base = [3, 0, 0], filled = 1, patch = [-8, -5], added = 2
Output: [-8, -5, 3]

Both arriving deltas are colder than everything the station probe logged, so the single existing reading is pushed to the end.

Example 3

Input: base = [6], filled = 1, patch = [], added = 0
Output: [6]

The second probe recorded nothing, so there are no reserve slots and the log is already in order.

Constraints

base.length == filled + added
patch.length == added
0 <= filled, added <= 200
1 <= filled + added <= 200
-10^9 <= base[i], patch[j] <= 10^9
The first filled entries of base and all of patch are each in non-decreasing order
Only a constant amount of extra space may be used

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 merge_log(base: list[int], filled: int, patch: list[int], added: int) -> list[int]:

Java

public int[] mergeLog(int[] base, int filled, int[] patch, int added)

The intended approach

Time O(filled + added)Space O(1)

Fill `base` from its last position backwards. Compare the largest unplaced delta on each side and write the bigger one at the write cursor, which always sits at or after the position being read, so no unread reading is ever clobbered. Once `patch` is exhausted the remaining station readings are already parked in their final spots, so the loop can stop.

Pythonentry point: merge_log

def merge_log(base, filled, patch, added):
    i = filled - 1
    j = added - 1
    write = filled + added - 1
    while j >= 0:
        if i >= 0 and base[i] > patch[j]:
            base[write] = base[i]
            i -= 1
        else:
            base[write] = patch[j]
            j -= 1
        write -= 1
    return base

The obvious version

Copy the real prefix of base together with all of patch into a scratch list, sort it, and write it back over base position by position. Uses extra space and a sort, so it is only here to be obviously correct.

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_merge_log(base, filled, patch, added):
    scratch = list(base[:filled]) + list(patch[:added])
    scratch.sort()
    out = list(base)
    for idx, value in enumerate(scratch):
        out[idx] = value
    return out

How this problem was checked

Reference solution executed against 11 test cases — 11 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