Merge Sorted Array
Last Updated: March 21, 2026
Understanding the Problem
On the surface, this is a classic merge operation from merge sort. But there's a twist: we have to merge in-place into nums1, which already has extra space at the end to hold all elements from nums2.
The natural instinct is to merge from the front, comparing the smallest elements first. But that creates a problem: if nums2[0] is smaller than nums1[0], placing it at the front of nums1 would overwrite a value we haven't processed yet. We'd need to shift elements right, turning what should be a linear operation into O(m \* n).
The key observation is that the back of nums1 is empty (filled with placeholder zeroes). If we merge from the back instead, placing the largest elements first, we'll never overwrite anything we still need.
Key Constraints:
0 <= m, n <= 200→ With m + n at most 400, even O(n^2) runs in microseconds. But the follow-up explicitly asks for O(m + n), so we should aim for that.nums1.length == m + n→ The extra space at the end of nums1 is exactly enough to hold all elements from nums2. This is a strong hint that an in-place solution exists.-10^9 <= nums1[i], nums2[j] <= 10^9→ Values fit in a 32-bit integer. Negative numbers are possible, so don't assume values are positive.
Approach 1: Sort After Merge
Intuition
The most straightforward approach: don't bother merging carefully at all. Just copy all elements from nums2 into the empty slots at the back of nums1, then sort the entire array. The built-in sort handles the rest.
This completely sidesteps the merging logic. It's brute force in the sense that it ignores the fact that both arrays are already sorted, treating the problem as a generic "combine and sort" task.
Algorithm
- Copy each element from
nums2intonums1starting at indexm. - Sort the entire
nums1array.
Example Walkthrough
Code
- Time Complexity: O((m + n) log(m + n)). Copying takes O(n). Sorting takes O((m + n) log(m + n)). The sort dominates.
- Space Complexity: O(log(m + n)). Most built-in sorting algorithms use O(log n) stack space for recursion. No extra array is needed.
Since both arrays are already sorted, can we take advantage of that structure to merge them in a single linear pass instead of re-sorting everything?
Approach 2: Three Pointers (Merge from End)
Intuition
Both arrays are sorted, so we know the largest elements are at the ends. And the back of nums1 is empty, waiting to be filled. So here's the idea: start from the back of both arrays, compare the two largest unplaced elements, and put the bigger one at the end of nums1. Then move the pointers backward.
Why does merging from the back work while merging from the front doesn't? If we merge from the front, placing a small element from nums2 at the start of nums1 would overwrite a valid element. But when we merge from the back, we're writing into the placeholder slots (indices m through m+n-1). By the time we reach an index that holds a valid nums1 element, that element has either already been moved to its final position or is still waiting at a lower index. There's no conflict.
The correctness relies on a simple invariant: at every step, the write pointer k is always at or ahead of the read pointer i. The pointer k starts at m + n - 1 and i starts at m - 1, so k - i = n. Every iteration, k decreases by 1. The pointer i decreases by at most 1 (only when we pick from nums1). So the gap k - i either stays the same or grows. It never shrinks below n, which is at least 0. This means we never overwrite a value in nums1 that we haven't read yet.
Also note that if nums2 is exhausted first, the remaining nums1 elements are already in their correct positions at the front of the array. They never needed to move. Only leftover nums2 elements need to be copied.
Algorithm
- Initialize three pointers:
i = m - 1(end of valid elements in nums1),j = n - 1(end of nums2), andk = m + n - 1(end of nums1). - While both
i >= 0andj >= 0: - If
nums1[i] > nums2[j], placenums1[i]at positionkand decrementi. - Otherwise, place
nums2[j]at positionkand decrementj. - Decrement
k. - If there are remaining elements in
nums2(j >= 0), copy them into nums1. - No need to handle remaining elements in
nums1since they're already in place.
Example Walkthrough
Code
- Time Complexity: O(m + n). Each element from nums1 and nums2 is placed exactly once. The first while loop handles at most m + n iterations, and the cleanup loop handles at most n iterations, but in total we place exactly m + n elements.
- Space Complexity: O(1). Only three integer pointers. No extra arrays or data structures.