88. Merge Sorted Array
Asked at Google, Amazon, Microsoft, Oracle and 1 more
Difficulty
Easy
Time
O(m + n)
Space
O(1)
Pattern
Array
Companies
5
Problem
You get two arrays of integers, nums1 and nums2, both already sorted from small to large. You also get two counts: m is how many real values live in nums1, and n is how many values live in nums2.
Your job is to merge nums2 into nums1 so that nums1 ends up holding all m + n values in sorted order. Do not return a new array — you must change nums1 in place.
To make room, nums1 has length m + n. The first m slots hold real values. The last n slots are just placeholders (they contain 0) and must be ignored on input. nums2 has exactly n values.
Merge nums2 into the free space of nums1
Constraints
- ●
nums1.length == m + n - ●
nums2.length == n - ●
0 <= m, n <= 200 - ●
1 <= m + n <= 200 - ●
-10^9 <= nums1[i], nums2[j] <= 10^9
Examples
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3[1,2,2,3,5,6]nums1 = [1], m = 1, nums2 = [], n = 0[1]nums1 = [0], m = 0, nums2 = [1], n = 1[1]Asked At
5 companies| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Oracle | Easy | View all Oracle questions → |
| Bloomberg | Easy | View all Bloomberg questions → |
How to Think About It
Brute force: merge both arrays into a new array, sort it, copy back. That's O((m+n) log(m+n)) -- you lose the fact that both arrays are already sorted.
Better approach: use two pointers starting from the beginning. Compare elements and copy the smaller one to a temporary array. Then copy back. That's O(m+n) time but O(m+n) extra space.
Key insight: fill nums1 from the END. Start comparing from the last elements of both arrays. The largest element goes to position m+n-1. This way, you never overwrite elements you haven't read yet.
Why from the end: nums1 has extra space at the end (indices m to m+n-1). By filling from the back, you use that empty space. If you fill from the front, you'd overwrite nums1 elements before reading them.
Edge cases: nums2 is empty (nothing to merge). nums1 is empty (just copy nums2). All elements in nums2 are smaller (nums1 shifts right). All elements in nums2 are larger (appended at end).
Optimal Approach
Step 1: Initialize three pointers: p1 = m-1, p2 = n-1, write = m+n-1.
Step 2: While p1 >= 0 and p2 >= 0:
- If nums1[p1] > nums2[p2], set nums1[write] = nums1[p1], decrement p1
- Otherwise, set nums1[write] = nums2[p2], decrement p2
- Decrement write
Step 3: If p2 >= 0 (nums2 has remaining elements), copy them to nums1[0..p2].
Step 4: If p1 >= 0 (nums1 has remaining elements), they're already in place.
Walkthrough for nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3:
- p1=2, p2=2, write=5
- nums1[2]=3 < nums2[2]=6: nums1[5]=6, p2=1, write=4
- nums1[2]=3 < nums2[1]=5: nums1[4]=5, p2=0, write=3
- nums1[2]=3 > nums2[0]=2: nums1[3]=3, p1=1, write=2
- nums1[1]=2 == nums2[0]=2: nums1[2]=2, p2=-1, write=1
- p2 < 0, done. nums1[0..1] = [1,2] already in place.
- Result: [1,2,2,3,5,6]
Time: O(m+n) -- each element is moved at most once. Space: O(1) -- in-place merge.
Fill from the back with three pointers
What Trips People Up in Real Interviews
Merging from the front instead of the back. If you start from index 0, you overwrite nums1 elements before reading them. Always merge from the end using write = m + n - 1.
Forgetting to copy remaining nums2 elements after the main loop. When p1 runs out but p2 still has elements, those must be copied into nums1[0..p2]. Remaining nums1 elements are already in place.
Not initializing p1, p2, and write correctly. p1 = m - 1 (last real element of nums1), p2 = n - 1 (last element of nums2), write = m + n - 1 (last slot). Off-by-one here breaks everything.
Confusing this with merge two sorted arrays into a new array. This problem requires in-place merging with no extra space, which is why the reverse traversal is essential.
Using a two-pointer approach from the front with a temporary array. While that works in O(m+n) time, it uses O(m+n) extra space. The interviewer expects the O(1) space reverse-merge solution.
Solution Code
O(m + n) timedef merge(nums1, m, nums2, n):
p1, p2, write = m - 1, n - 1, m + n - 1
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[write] = nums1[p1]
p1 -= 1
else:
nums1[write] = nums2[p2]
p2 -= 1
write -= 1
while p2 >= 0:
nums1[write] = nums2[p2]
p2 -= 1
write -= 1Frequently Asked Questions
What is the Merge Sorted Array problem?
Given two sorted arrays nums1 and nums2, merge nums2 into nums1 in-place. nums1 has a length of m + n, with the first m elements being the actual values and the rest being placeholders. This problem tests your ability to merge from the end to avoid overwriting elements.
How do you solve Merge Sorted Array?
The optimal approach runs in O(m + n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Merge Sorted Array?
Merge Sorted Array is asked at Google, Amazon, Microsoft, Oracle, Bloomberg. It is a easy difficulty problem.
What are common mistakes on Merge Sorted Array?
- Merging from the front instead of the back. If you start from index 0, you overwrite `nums1` elements before reading them. Always merge from the end using `write = m + n - 1`.
- Forgetting to copy remaining `nums2` elements after the main loop. When `p1` runs out but `p2` still has elements, those must be copied into `nums1[0..p2]`. Remaining `nums1` elements are already in place.
- Not initializing `p1`, `p2`, and `write` correctly. `p1 = m - 1` (last real element of `nums1`), `p2 = n - 1` (last element of `nums2`), `write = m + n - 1` (last slot). Off-by-one here breaks everything.
- Confusing this with merge two sorted arrays into a new array. This problem requires in-place merging with no extra space, which is why the reverse traversal is essential.
- Using a two-pointer approach from the front with a temporary array. While that works in `O(m+n)` time, it uses `O(m+n)` extra space. The interviewer expects the `O(1)` space reverse-merge solution.