DiffPush Tier Arrays · Hard O(m + n) · O(1)
A logging service keeps its primary index in a preallocated array whose tail slots are reserved for a standby batch, both already sorted by event id. On flush, the standby entries must be folded into the primary buffer so the whole thing reads sorted, without allocating another buffer. The primary array is exactly sized to hold both sets.
Input: An array nums1 of length m + n holding m sorted entries followed by n reserved slots, an integer m, an array nums2 of length n, and an integer n.
Output: nums1 rewritten in place so its first m + n cells hold all entries in non-decreasing order. nums2 is not part of the result.
nums1.length == m + n0 <= m, n <= 2001 <= m + n-10^9 <= nums1[i], nums2[j] <= 10^9The merge must happen in place with no extra arrayInput: {"nums1":[1,2,3,0,0,0],"m":3,"nums2":[2,5,6],"n":3}
Output: [1,2,2,3,5,6]
The reserved slots are exactly enough for the standby entries, which interleave into the primary index in order.
Input: {"nums1":[1],"m":1,"nums2":[],"n":0}
Output: [1]
An empty standby batch leaves the primary index untouched.