You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, along with two integers m and n giving how many real elements each holds.
Merge nums2 into nums1 so that nums1 becomes one sorted array. The merged result must be stored inside nums1: the function returns nothing.
To make room, nums1 has length m + n — its first m slots hold its real values, and the final n slots are 0 placeholders you may overwrite. nums2 has length n.
How your function is called
merge(nums1, m, nums2, n) → nothing; nums1 is mutated in place
The judge builds nums1 (the first m sorted values plus n trailing zeros) and nums2, calls your merge, then reads back the full nums1.
nums1 get overwritten?nums1. Fill it from the back, largest element first, using three pointers.nums1's own unprocessed values before you've placed them. The empty room is at the end, so filling from the back — largest first — never clobbers data you still need.Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Merging [1,2,3] and [2,5,6] gives [1,2,2,3,5,6]. The result fills nums1.
Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] nums2 is empty, so nums1 is already the merged result.
Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] m = 0 means nums1 has no real elements; the answer is just nums2.
- nums1.length == m + n - nums2.length == n - 0 <= m, n <= 200 - 1 <= m + n <= 400 - -10^9 <= nums1[i], nums2[j] <= 10^9 - nums1 (first m) and nums2 are each sorted in non-decreasing order.
Merge Sorted Array looks trivial until the in-place constraint bites: you must write the answer into nums1 itself, whose front slots are still holding data you need. The elegant fix — merge from the back, into the free space — is a small idea with a big payoff, and it's exactly the combine step of merge sort run in reverse.
Given sorted nums1 (with m real values and n trailing placeholders) and sorted nums2 (with n values), merge them into nums1 in place. The function returns nothing.
Worked example — nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
fill from the back, larger tail first: 6 → 5 → 3 → 2(from nums2) → then nums1's [1,2] already sit in front nums1 = [1, 2, 2, 3, 5, 6] ✓
“Is nums1 already sized to m + n, with its last n slots free?”
Yes — that spare room at the end is exactly what the in-place merge writes into.
“Are both halves sorted non-decreasing?”
Yes — that's what makes it a merge (O(m+n)) rather than a full sort.
“What if n = 0 (nums2 empty)?”
nums1 is already the answer; nothing is written.
“What if m = 0?”
nums1 has no real values, so the result is nums2 copied in.
“Do I return anything?”
No — mutate nums1 in place. The judge reads nums1 back after the call.
“Is O(1) extra space expected?”
Yes — the back-to-front merge uses nums1's own free space, no auxiliary array.
A couple of questions.
nums1 is already length m + n, with its last n slots as free placeholders?
I merge in place and return nothing?
Since the free space is at the end, I'll merge from the back with three pointers — O(m+n), O(1).
Both inputs are already ordered, so you never need to compare arbitrary pairs — the next element of the answer is always at the front (or, here, the back) of one of the two halves. That's O(m+n), not the O((m+n) log(m+n)) a full sort would cost.
nums1's real values occupy its front slots. If you wrote the merged result front-to-back, you'd overwrite those values before placing them. But the free room is at the end — so fill from the back, largest element first, and the write pointer always lands on already-empty space.
Point i at nums1's last real element, j at nums2's last, and k at nums1's final slot. Copy the larger of the two tails to k and step inward. When nums2 runs dry, any remaining nums1 elements are already sitting in their correct front positions — no cleanup needed.
| Copy then sort | Merge from the back | |
|---|---|---|
| Idea | Dump nums2 into the tail, sort all | Three pointers, largest first |
| Time | O((m+n) log(m+n)) | O(m+n) |
| Space | O(1) | O(1) |
| Uses sortedness |
The full code for both is in the Approaches selector below.
Key takeaway
To merge two sorted arrays in place when the spare room is at the end, fill from the back with three pointers, taking the larger tail each step. The write pointer always trails on emptied slots, so nothing is overwritten — O(m+n) time, O(1) space. It's merge sort's combine step, run in reverse to reuse the destination's own free space.