Show problems as
Classic problem #88EasyArrayTwo PointersSorting

Merge Sorted Array

Real-world version: Merge Into the Padded Log
Tracked in this browser only
Read Merge Sorted Array on LeetCode(opens in a new tab)

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

Learn the pattern firstSorting · Arrays, animated step by step

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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard 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)

More on the same topics